Ball breaking
Your job is to determine the highest floor of a 100 floor building from which a snooker ball may be dropped without breaking. You have two identical snooker balls. If a ball doesn't break, it is completely unharmed. If both balls break before you have determined the highest floor, or you drop the balls more times than is necessary, then you'll need to to seek alternative employment. What is the maximum number of times you have to drop the balls?
For consistency, assume the floors are numbered 1 to 100 in your explanations. Also assume, that there is no need to drop a ball from floor 1 (the ground floor).
For consistency, assume the floors are numbered 1 to 100 in your explanations. Also assume, that there is no need to drop a ball from floor 1 (the ground floor).
Labels: logic, mathschallenge
posted by Chris at
2:12 AM
28 Comments:
42: Start with floor 2, then 4, then 8 until 64. If the ball is still not broken you need 36 more.
To start the ball rolling (sorry) I'll say 50 times.
Drop one ball from each even numbered floor, starting from the second floor, until a ball breaks. Then drop your second ball from the floor below. If it survives, then you've found the floor. If it breaks, then it's the floor below (which is the last even numbered floor from which the ball didn't break).
I've assumed that your 100 floors includes the ground floor, so that the top floor would be the 99th floor in UK notation (and 100th in US notation).
Thus, if you get to the 98th floor (UK notation)on your 49th drop, and the ball doesn't break, then another drop from the top floor is needed to see if this is the highest.
You're both way out.
For this problem, assume the floors are numbered 1 to 100 and not in my crazy British system. I'll amend the question for that.
Call the manufacturer and request a copy of the engineering stress test report ... heh heh!
Upon receipt of the engineering stress test report, read it, enjoy it, and then properly place it in file 13, because it has nothing to do with the stated problem ... heh heh.
Seems to me Oz is right unless it's a lateral thinking question. Since, Chris, you say he's way out I'm going to hazard a guess that it is.
If so, I think the answer is only 1 drop is required.
Drop the ball from the 100th floor, but drop it on the inside (which isn't prohibited as you've stated the problem). Since it only falls within that floor, it won't break, or if it does, it would break on any of the floors.
Actually, using that logic, you don't actually need to test it at all so you could use the balls to learn to juggle instead!
You are the manufacturer conducting the tests so that people can phone you up to find out how high... ;)
Mr. F, well done, there are now so many career opportunities for you to choose from. i.e. wrong answer ;)
7 drops
Well I hear that there are lots of jobs going for jugglers who juggle with two balls :)
I ammend my previous answer to either 7 or 8 drops ... one drop may be needed to verify ... can't further analyze right now ... gotta run to the doc ...
must be a pretty rough billiards parlor if snooker balls are being thrown from the windows
I'm new here, so, since it's called trick of mind, there can be multiple answers, but i will go with:
0, you don't need to drop the BALLS, you only need to drop A ball starting from floor 1 to floor "n" where it will break, "n" being the maximum number of drops, and n-1 is the floor from which you can safely drop a snooker ball.
(i considered
1. the balls are identical
2. they have 2 states, intact and destroyed
3. i need "to determine the highest floor ... from which A snooker ball may be dropped without breaking")
My new answer is 35.
This would be the case if floors 98 or 99 were the highest that the balls could survive from.
We are told floor 1 is safe. Next go to floor 4.
If ball A breaks from floor 4, use ball B on floor 2. If it breaks then floor 1 is the highest; if it doesn't then test at floor 3 to determine which of floor 2 or floor 3 is the highest that it can be dropped from.
If ball A doesn't break (from floor 4) go to floor 7 and apply the same procedure, then 10, 13, 16 and so on in multiples of 3 up to 100.
Once ball A breaks go down two floors and test ball B. If it survives go up one floor and test it again.
Hi Zaux.I take it you've run out of your meds.
Hi Mirel. Usually the other answers are joke ones and there is only one "proper" answer. Also, the problems should not (usually) be considered as real-life ones. The underlying logic/maths (or whatever) is what it's really about. The stuff about snooker balls (or whatever) is just mind candy. You should suspend your disbelief when doing the problems.
You're right in that you could just keep going up one floor, but the question asks yo to do it in the minimum number of drops. i.e. find a strategy which minimises the number of drops, then determine what the maximum/worst-case number is using that strategy.
Hint, it's greater than 8 and less than 35.
Neat puzzle, I am really enjoying your site!
If we divide the building into 2 story sections, we need 50 drops, plus 1t figure the minimum floor in the set. 51 drops.
If we divide the building into 3 story sets, we need 33 drops, plus 1 (test 2nd floor in the set). 34 drops.
4 story sets need 25 plus 2 drops for 27 drops.
5... 20 + 3 = 23.
6... 16 + 4 = 20.
7... 14 + 5 = 19.
8... 12 + 6 = 18.
9... 11 + 7 = 18.
18 drops. Interestingly, it seems to be 18 if you do 8, 9, 10, 11, 12, or 13 floor groups.
Tah dah?
Now I'm annoyed. Mainly cos I've not got any work done.
To minimise the number of test you need to get the right balance between number of floors
between each test. So you could go up in multiples of 3 like my previous post, but then you have to do that potentially up to
33 times. However, if you go in multiples of 4 then it's down to 25, if in multiples of 5 = twenty, 6 = seventeen, 7 = fifteen, 8 = 13 and so on.
But if the ball breaks you have to go the previous floor you tested plus one, and then test each subsequent floor up until you reach one below where you just came from.
e.g. if ascending in multiples of 5
You test floor 6. Ball A survives.
You test floor 11. Ball A breaks.
You then test floor 7, 8 9,10. Since you have only one ball left at this point you can't really do anything clever like testing the middle floors like floor 8 before floor 7.
So generally, if you ascend X floors between tests until ball A breaks and then
at most X-1 tests on ball B
If X = 3 most tests, is 35
If X = 4 most tests is 27
If X =5 most tests is 23
If X=6 most tests is 21
If X=7 most tests is 20
If X=8 most tests is 19
If X=9 most tests is 19
If X=10 most tests is 18
If X=11 most tests is 19
If X= 12 most tests is 19
I'm going to stop there. So it seems to me that the way to guarantee fewest tests is
to hop up 10 floors each time. This gives a maximum of 19 tests. However, depending on
which floor is actually the limit, you could obviously do it in fewer, and this raises the interesting
question, for a given floor x (x being the highest floor from which a ball can be dropped and not break),
which is the fewest number of tests that could be done. If you were then to run x from 1 to 100 and work out the best strategy for each floor, it may differ. Or alternatively, my brain might have just exploded. Help!
Hi Chris ... nah, I've still got plenty of meds ... had to go for a cat scan ... go this afternoon for a bone scan.
Zaux. That doesn't sound too good.
Mr. F., I'm sure there are some wonderful jobs out there which don't involve breaking your thingies. However, you've got a reprieve as you're starting to do the right sort of thinking. At least you've got the upper limit down from 35 to 18.
I suppose I'd better start working out how to do it myself soon.
Just in case it's not obvious, it's alright if both balls are broken at the end, as long as you have worked out the lowest floor at which the balls break. Also it is possible (in principle) that 100 floors isn't high enough.
Mister Farenheit is right, I think.
Actually, the worst case number of tries can be written as int(100/n)+n-2, where int(x) is the larger integer less then or equal to x.
The minimum of the function f(x)=100/x+x-2 is attained at x=10, where f(x)=18.
Using the policy described by Mister Farenheit, 18 is the optimal worst case trial number, and 10 the floor interval you should use.
Miguel, I know a better answer (I posted the problem) so I know that Mr F isn't right (yet!)
Although I know the answer, I haven't seen a demonstration that it is the best, but I suspect that it is. Usually the source only contains the result, not how the result is obtained. So if no-one gets it, I'll work out a proper answer. I hate only seeing the result. For me, the method of getting it is much more interesting, especially if it is elegant.
Start on the 14th floor- 13 drops
move up 13 floors -13 total drops if on this section
move up 12 floors- 13 total drops if on this section
move up 11 floors 13 total drops if on this section
Continue until you reach the 100th floor
This results in 13 maximum drops.
whoops i guess that doesn't quite work does it. Don't use i<= to 1 in c++ when it should be i < 1.
And yes it should be floor 15.
David and Kimmy. OK after my deleted announcement, I can definitely call you the winners. Well done. And I know how you did it.
Sorry about removing the post, I had mucked up a bit myself.
Starting at floor 15. If the ball broke, then go down to floor 2 and drop, if ball doens't break, go to floor 3 etc. At worst you get to floor 14, using a total of 14 drops.
If the ball didn't break at floor 15, you nip up to floor 28 (=15+13). If the ball broke you go down to floor 16 and start dropping from there. If it didn't break at floor 28, you'd go up to floor 40 (=15+13+12).
In fact you could have had a 106 floor building and do it in 14.
Anyone care to determine the maximum number of floors if you accept M as the max number of drops?
I've got a solar system to cut down to size.
If m is the max number of drops, then can do 1 + m(m+1)/2 floors.
If have f floors, then m = ceiling[(sqrt(8f-7) -1))/2]
Formula are a slightly nicer if use the UK system, G,1,2,3,...,F
i.e. F = f-1 => f = F+1 =>
F = m(m+1)/2 and m = ceiling[(sqrt(8F+1) -1)/2]
I should have taken the series a tad further.
In cryptic brief notation get:
15+13+12+11+10+9+8+7+6+5+4+3+2+1
15,28,40,51,61,70,78,85,91,96,100,103,105,106 are the starting floors.
In this case, I'm not going to bother formally developing a strategy, as the numbers should make everything self-evident. It also seems pretty obvious that there isn't a better strategy.
Very minor point. I could have said that floor 1 is to be included in the tests. Then would have started at floor 14 and could have gone up to floor 105 (if it existed).
Post a Comment
Links to this post:
Create a Link
<< Home