WRT the first one: I know it's correct, you just didn't have it explicitly in your proof, and showing that part is true is required to showing the final result is true.
I was just being a pedant.
No worries - my response was my proof for that section. If there's ever a time to be pedantic, it's with math proofs!
Quote:
Originally Posted by Bring_Back_Shantz
WRT the second, I figured it wasn't optimal, but a good first pass/starting point. I'll have to think a bit more.
I think you're on the right track - keep plugging away!
Location: In my office, at the Ministry of Awesome!
Exp:
Spoiler!
I managed to do better and get it down to 15 minimum drops.
First drop is N=1
Second drop is N =2
First floor you drop it from is floor F
Best case is F = 14
For each drop you go up F-(N-1) floors (assuming it doesn't break).
Drop 1 = 14-(1-1) = floor 14
Drop 2 = 14 + (14-(2-1)) = floor 27
Drop 3 = 27 + (14-(3-1)) = floor 39
Once it breaks you then go back to and drop it from each floor one by one from the last floor it broke on until it breaks.
So if it breaks on the 2nd drop (floor 27), you then go back to 15 and drop 1 by 1 (15-26 = 12 drops + the you already dropped)
When the first egg drops you'll have dropped it N times, and the number of drops between the safe floor, and broken floor is N-2), so you no matter where it breaks your maximum number of drops is
N + F -(N-2) = F
The minimum is where your number of big drops, and the final number of drops between that and 100 (assuming you have to go through the final interval) is a minimum.
I haven't taken the time to generalize the numbers, but it looks like it's at 14.
I'll see if I can figure out the general equation.
Edit: Okay I've generalized it
You need a starting floor where you can get to 100 before the interval between drops gets to zero otherwise you'll get to your number F and will require more steps to check up to 100, so your total number of drops will be at least F+1.
Highest floor you can get to is
F + (F-1) + (F-2) etc
it's a sum of the numbers from 1 to F
So the max you can get to is (F+1)*(F/2)
The first number that gets above 100 is 14: (14+1)*(14/2) = 105
So for any building up to 105 floors, you'll always be able to figure out how high the egg can be dropped within 14 drops.
__________________
THE SHANTZ WILL RISE AGAIN. <-----Check the Badge bitches. You want some Awesome, you come to me!
Last edited by Bring_Back_Shantz; 08-15-2022 at 05:09 PM.
I assume this has been solved by others but before I look the balance appears to be having the hundredth floor break your egg needing 99 floor to be successful and the n-1 floor after any drop and having to test from your last successful drop.
So you need to start at whatever floor exceeds the floor number by the least decreasing the drop spacing by 1 each time. So checking with the (N+1)*N/2 is least over 100 so 13 is 91 and 14 is 105. So I think max it will take is 14 drops.
The Following User Says Thank You to GGG For This Useful Post:
I had another good number theory type problem, but I'll do that later. People seem to enjoy the more "practical" ones. So try this one.
You have two balls made of some new substance, and you want to determine the highest floor of a 100 storey building from which you can drop a ball and have it not break. Once a ball breaks, it can't be used again.
The brute force method would be to start at the first floor, and keep dropping a ball until it breaks. Then the previous floor would be the answer. This could take up to 100 drops, however (assuming the first floor starts above the main floor).
What's the minimum number of drops you must make to figure this out?
Spoiler!
1, if it happens to break on the first drop
But I assume what you're actually asking about is the minimum maximum (i.e. the minimum assuming the worst possible outcome for your algorithm).
Trial and error musings:
Spoiler!
First instinct was drop in the middle, reduce requirement in half. But then, if survives, you still have two balls. Next, considered dropping at 1/3rd... but the size of the group needed to brute force was decreasing too fast. Guesstimate 1/4?
Drop it from 25 ... if it breaks, brute force from 1 to 24 (25 total)
If it does not break, you still have two balls. Drop it from 44. If it breaks, brute force from 26 to 44 (drop at 25, drop at 44, 26 to 44= 21 total).
If it does not break, drop from 58. If it breaks, brute force from 45-57 (drops at 25,44,58 + 45 to 57 = 16 total).
If it does not break, drop from 69. If it breaks, brute force from 59-68 (drops at 25,44,58,69 + 59 to 68 = 14 total).
If it does not break, drop from 77. If it breaks, brute force from 70-78 (drops at 25,44,58,69,77 + 70 to 78 = 14 total).
If it does not break, drop from 85. If it breaks, brute force from 78-84 (drops at 25,44,58,69,77,85 + 78 to 84 = 13 total).
If it does not break, drop from 90 . If it breaks, brute force from 86-89 (drops at 25,44,58,69,77,85,90 + 86 to 89 = 11 total).
If it does not break, drop from 93...
Pattern: for the the total number of drops to be maintained the size of the brute force group decreases by 1 each time.
Working backwards, brute force groups:
If it breaks when you drop at 100, brute force 99.
If it breaks when you drop at 98, brute force 96 to 97.
If it breaks when you drop at 95, brute force 94 to 92.
If it breaks when you drop at 91, brute force 87 to 90.
If it breaks when you drop at 86, brute force 81 to 85.
If it breaks when you drop at 80, brute force 74 to 79.
If it breaks when you drop at 73, brute force 66 to 72.
If it breaks when you drop at 65, brute force 55 to 64.
If it breaks when you drop at 54, brute force 45 to 53.
If it breaks when you drop at 44, brute force 34 to 43.
If it breaks when you drop at 33, brute force 22 to 32.
If it breaks when you drop at 21, brute force 9 to 20.
If it breaks when you drop at 8, brute force 1 to 7.
I.e. in the sequence
Drop at 8 (1)
If it breaks when you drop at 8, brute force 1 to 7. (8 total)
Otherwise, drop at 21. (2)
If it breaks when you drop at 21, brute force 9 to 20. (14 total)
Otherwise, drop at 33. (3)
If it breaks when you drop at 33, brute force 22 to 32. (14 total).
...
So yeah, 14.
Will wait for psyang's answer to me before looking at the rest of your spoilers.
I can say that Bring_Back_Shantz, GGG, and SebC all have correct solutions, though not all are identical. I think it's interesting that SebC worked backwards for their solution, and so has basically the reverse solution of the other two.
Based on timestamps, BBS answered first. Great job!
I do enjoy reading your musings/reasonings for your solutions. Extra points to BBS and GGG for coming up with the general formula to solve this for a building with n floors.
Alice, Bob, and their dog Cujo all start at the same point. Alice and Bob begin walking down the same path in the same direction: Alice walks at 4km/h, Bob at 3km/h. Cujo, meanwhile, runs back and forth on the path between Alice and Bob at 10km/h (ie. he runs until he meets Alice, then immediately turns around and runs until he meets Bob then turns around again to run to Alice etc, always staying on the path).
Assume they all travel at constant speed the entire time.
After 1 hour, Alice is 4km down the path from the start point. Bob is 3km on the path from the start point. Where on the path is Cujo?
I want to revisit this problem. GGG solved it, but wasn't happy with the paradox it seemed to create.
In thinking this over some more, I have to agree and I think the solution should be:
Spoiler!
It is an impossible question. The reason Cujo can seem to appear anywhere between A and B is similar to those proofs that 1=2 because of a divide-by-0 error.
A couple thought experiments.
1) Suppose Alice had an infinitely small head start. In that instance, the problem is completely solvable, and C will end up in a specific spot between A and B. This leads me to think that the initial condition where A, B, and C all start at the same point is an asymptote.
2) To remove the problem of A, B, and C accelerating to their speeds instantaneously at the start, consider this revision. A starts 4km before the starting point. B starts 3km before the starting point, and C starts 10km before the starting point. They travel towards the starting point, and after 1 hour, hit that point simultaneously. A and B continue travelling as usual, but C is now restricted to travel between A and B. What happens?
It is, in fact, impossible. After exactly an hour, C cannot continue travelling at 10km/h and remaing between A and B because the distance between A and B is now 0. This is the divide-by-0 error.
The problem, as set up, is not possible, which is why C appears to be able to exist anywhere between A and B.
The only other solution I thought of is if you allow C to travel in the third dimension (ie. jumping). In this case, C can jump to maintain a speed of 10km/h but still remain between A and B. C's trajectory will determine how high, but more importantly, how far along the path he travels. There will be a range of jump angles that C can choose from to ensure C lands between A and B each time. As such, depending on those trajectories, C can end up anywhere between A and B an hour after they "start" at the same point.
The problem with this idea, though, is that C cannot maintain a constant 10km/h speed during the jump since the vertical speed component of the jump will be diminished by gravity, resulting in a lower overall speed.
__________________
"An idea is always a generalization, and generalization is a property of thinking. To generalize means to think." Georg Hegel
“To generalize is to be an idiot.” William Blake
Correct! I hope anyone else who is stumped will take some serious time to try to solve it before looking at the answer. It's a great example of misdirection.
In response to psyang thoughts on the dog problem. I butchered the quoting so deleted it all.
Spoiler!
I don’t think it’s a divide by zero error. It’s just you have insufficient information about the initial conditions of the problem because your start at an infinitesimal distance.
Remember the fly problem in reverse if two trains are traveling toward each other and a fly travels in between how long does it take for the fly to get squished.
It doesn’t matter where the fly starts it gets squished when the trains collide. So that problem works backwards and it shows that the end point of the dog (starting point of the fly) doesn’t actually matter and can be anywhere.
It’s essentially behaves like an integration constant, it can be any value. You take an equation take the derivative then take the integral and you don’t get the same
Equation back. You lose information.
So the problem with the information given does have all possible locations as a solution. I don’t think it’s a divide by zero problem.
Last edited by GGG; 08-27-2022 at 09:52 PM.
The Following 2 Users Say Thank You to GGG For This Useful Post:
In response to psyang thoughts on the dog problem. I butchered the quoting so deleted it all.
Spoiler!
I don’t think it’s a divide by zero error. It’s just you have insufficient information about the initial conditions of the problem because your start at an infinitesimal distance.
Remember the fly problem in reverse if two trains are traveling toward each other and a fly travels in between how long does it take for the fly to get squished.
It doesn’t matter where the fly starts it gets squished when the trains collide. So that problem works backwards and it shows that the end point of the dog (starting point of the fly) doesn’t actually matter and can be anywhere.
It’s essentially behaves like an integration constant, it can be any value. You take an equation take the derivative then take the integral and you don’t get the same
Equation back. You lose information.
So the problem with the information given does have all possible locations as a solution. I don’t think it’s a divide by zero problem.
Spoiler!
The difference with the fly/train puzzle is that the fly will get squashed at different times depending on where it starts. Its position is completely deterministic at any point in time given known initial conditions.
In the dog problem, the dog can be at any location at the same time.
What hammered home the issue for me is the first thought experiment I mentioned - if A starts along the path with a small epsilon headstart (ie. an inifinitely small but non-zero headstart) the problem becomes completely deterministic. But once that headstart hits 0, it becomes non-deterministic.
Another thought experiment: if you take a snapshot at time=epsilon, you will see A has travelled a small amount, B has travelled a smaller amount, and you'd expect C to have travelled between A and B enough times to maintain its speed.
But for C to have travelled between A and B, it would have had to:
1) travel to A
2) travel to B
3) possibly repeat 1 and 2 enough times to ensure distance/time = C's speed.
But think of what is involved in step 1. Right at the start, C couldn't travel to where A is, because A travels slower than C. So it would immediately travel to where B is.
But by the same token, it couldn't travel to where B is by the same argument. It travels 0 distance in 0 time, which is where the divide by zero issue occurs.
It's a tricky problem and, because of the asymptotic nature of it, things like limits don't help.
The fly in the problem always gets squished at the same instant at the same position regardless of where it starts.
It’s squished at the instant the two trains collide regardless of where the fly starts if the trains haven’t colides yet the fly bounces. I don’t see how the initial position changes either the distance the fly travels or the instant it gets squished
The distance travelled is Vfly*time and the time to collision is D/(Vtrain1+Vtrain2) both are independent of the flys starting position.
At the instant the fly gets squished you have no way of knowing where that fly started.
Now maybe this loss of information is described as a /0 error but my argument would be that the solution of any position is a valid solution as opposed to one driven by error.
The fly in the problem always gets squished at the same instant at the same position regardless of where it starts.
It’s squished at the instant the two trains collide regardless of where the fly starts if the trains haven’t colides yet the fly bounces. I don’t see how the initial position changes either the distance the fly travels or the instant it gets squished
The distance travelled is Vfly*time and the time to collision is D/(Vtrain1+Vtrain2) both are independent of the flys starting position.
At the instant the fly gets squished you have no way of knowing where that fly started.
Now maybe this loss of information is described as a /0 error but my argument would be that the solution of any position is a valid solution as opposed to one driven by error.
I've gone back and forth on this a million times now and I can't fault your reasoning. I like your reframing the problem as the reverse of the train/fly problem. I was getting hung up on the impossibility of the initial conditions, but if we say that at the start everyone is at rest, then accelerates immediately to their constant speeds (essentially the reverse of when the fly is squished by the trains), we are ok.
We do have a winner here. Would anyone like to explain why?
Ok, here's the reasoning:
Spoiler!
It's clear that, after each iteration, the set is reduced by one element. So, after 95 iterations, the set will only contain one element.
It's also clear that, after 95 iterations, each of the original elements in the set will have been chosen as either a or b in our computation at least once.
Finally, it's clear that 1/2 is in our original set (48/96).
Now, suppose one of a or b is 1/2. Without loss of generality, let's say a=1/2
Then the computation gives:
x=2(1/2)b - (1/2) - b + 1
x=b - 1/2 - b + 1
x=1/2
So when 1/2 is chosen as a (or b), the item that replaces a and b will be 1/2.
This means that 1/2 can never be removed from the set, and since there is only 1 element left in the set after 95 iterations, it must be 1/2.
<-----Check the Badge bitches. You want some Awesome, you come to me!
