Breaking my balls

Originally posted by redriot16
you are on a path that eventually leads to a fork in the road. One way......whatever you may dream of (the right way)....and the other way.....your worst night mare (the wrong way). two brothers.....one always lies one always tells the truth (thos are the conditions under every circumstance) one question to find out the right way.....what question do you a ...[text shortened]... s is more of a riddle than a puzzle for those who like to be politically correct but whatever 🙂

Quit hijacking my thread, jerk. Especially since this question has been asked at least 3 times in the past month. 😠

Unless I'm missing something, this looks like a simple binary chop puzzle to me, in which case the answer is 7. In general the answer is 'n' where n is the smallest number such that 2 to the power of n is greater than the number of floors in the building.

Solution:

To start with let a = 0, b = 100

(start of loop)
If a is equal to b, then this value is the answer.
Let c = average of a and b (round down to nearest integer).
If c = a and you have already dropped from a then this is the answer.
Drop ball from floor c.
If ball breaks, let b = c.
If ball doesn't break, let a = c.
Go back to start of loop.

For example, imagine if the answer is 78.

Start with a = 0, b = 100.

(first loop)
c = (0 + 100) / 2 = 50.
Drop ball from floor 50.
It doesn't break, so let a = 50

(second loop)
c = (50 + 100) / 2 = 75
Drop ball from floor 75.
It doesn't break, so let a = 75

(third loop)
c = (75 + 100) / 2 = 87
Drop ball from floor 87.
It breaks, so let b = 87

(fourth loop)
c = (75 + 87) / 2 = 81
Drop ball from floor 81.
It breaks, so let b = 81

(fifth loop)
c = (75 + 81) / 2 = 78
Drop ball from floor 78.
It doesn't break, so let a = 78

(sixth loop)
c = (78 + 81) / 2 = 79
Drop ball from floor 79.
It breaks, so let b = 79

(seventh loop)
c = (78 + 79) / 2 = 78
c is equal to a, and we have already dropped from floor 78, so the answer is floor 78 and we needed to break six balls to get the answer.

EDIT: Sorry, my mistake I read it as having any number of glass balls, not just two. Since you stated that you only have two balls, I don't think the solution given works. I think the answer is 51. First try dropping a ball at floor 50. If it breaks try 1 to 49 in turn. If it doesn't break try 51 to 100 in turn.

Originally posted by Fat Lady
Unless I'm missing something, this looks like a simple binary chop puzzle to me, in which case the answer is 7. In general the answer is 'n' where n is the smallest number such that 2 to the power of n is greater than the number of floors in the building.

Solution:

To start with let a = 0, b = 100

(start of loop)
If a is equal to b, then this valu ...[text shortened]... floor 50. If it breaks try 1 to 49 in turn. If it doesn't break try 51 to 100 in turn.

Not only can you not read a simple puzzle you can't read the thread that follows it either.

Originally posted by XanthosNZ
Not only can you not read a simple puzzle you can't read the thread that follows it either.

Yes you're quite right. The bit I missed was that if you drop the ball and it doesn't break, you can use it again.

replying to my own stupidity............this is the first time i am getting aquainted with this site sooo excuse myself for the posting....wrong area.

i think its 7...

Originally posted by xtremechess1
i think its 7...

It ain't.

Great puzzle. And this solution would actually work for buildings up to 105 floors in height.
(Or 106 if you knew that the breaking strength was 106 or less.)

Originally posted by PBE6
Not sure if this one has been posted here or not, so here goes:

You are given 2 identical glass balls with the task of determining their breaking strength (you can assume that breaking strengths for each ball are equal). To do this, you have to drop the balls from different floors in a 100-story building and see if they break (again, you can assume that the ...[text shortened]... of drops you need to make to determine the breaking strength?

Hint: It's much less than 100.

The only problem with this is that when you're done you probably won't have any balls left. Anyone care to calculate the odds?

PB: Did you post this puzzle just so you'd have an excuse to post the thread title (which busts me up)? 😵

Originally posted by leisurelysloth
The only problem with this is that when you're done you probably won't have any balls left. Anyone care to calculate the odds?

PB: Did you post this puzzle just so you'd have an excuse to post the thread title (which busts me up)? 😵

You will have a ball left if the first floor from which the ball will break is a jumping point.
That is 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99.
This is the case because if you say dropped from 14 and broke and then dropped from 1-13 without breaking then you know that 14 is the breaking point and have one ball left.
Therefore if the probability of each floor is equal the chance is 11%.

However this isn't the end of the story as the original problem stated that the breaking point was 100 or less and therefore if you dropped from 99 and it didn't break you know that the breaking point is 100. And you have two ball remaining.
Therefore the probability is 12% and the expected number of balls remaining is 0.13 (0.11 + 2*0.01).

So now that I've answered a query I'll ask one. What's the generalisation for the minimum number of drops with N balls? Does it change?

Originally posted by XanthosNZ
You will have a ball left if the first floor from which the ball will break is a jumping point.
That is 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99.
This is the case because if you say dropped from 14 and broke and then dropped from 1-13 without breaking then you know that 14 is the breaking point and have one ball left.
Therefore if the probability of e ...[text shortened]... ne. What's the generalisation for the minimum number of drops with N balls? Does it change?

I'm not sure about the general case, but I'm sure the answer changes. If you've got balls enough, you could just do a binary search--searching 128 floors with 7 drops.

BTW, in the original problem, if I dropped ball #1 off the 99th floor and it still didn't break I'd probably suspect PB was lyin' to me and go toss the thing offa 100 just to check.

Originally posted by XanthosNZ
You will have a ball left if the first floor from which the ball will break is a jumping point.
That is 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99.
This is the case because if you say dropped from 14 and broke and then dropped from 1-13 without breaking then you know that 14 is the breaking point and have one ball left.
Therefore if the probability of e ...[text shortened]... ne. What's the generalisation for the minimum number of drops with N balls? Does it change?

I was thinking of the case with 100 balls and this would lead to the binary answer of 8 (I believe it has to be 8 because of the 0.5 nature of dividing 100). So this would be the lower limit. In fact if you had any more than 7 balls then you would only need 8 drops.

Originally posted by Gastel
I was thinking of the case with 100 balls and this would lead to the binary answer of 8 (I believe it has to be 8 because of the 0.5 nature of dividing 100). So this would be the lower limit. In fact if you had any more than 7 balls then you would only need 8 drops.

Actually I think you only need 7 drops. Any number up to 100 can be represented in 7 binary bits. Now if we start from the Most Significant Bit (64) then only a single drop is needed to test if each bit is contained in the number. Say the break point is 75, we drop from 64 and it doesn't break so we drop from 64+32=96 and it breaks and we continue:
1. 64 doesn't break
2. 96 breaks
3. 80 breaks
4. 72 doesn't break
5. 76 breaks
6. 74 doesn't break
7. 75 breaks
Therefore the answer is 75 (or 1001011). I haven't investigated fully so it could be possible I'm missing something but anyway with this method the number of balls we need is 7 (and you only need the 7th ball to determine whether the break point is 1 or 2).

So we have the following:
1 ball = 100 drops
2 balls = 14 drops
.
.
.
.
7 or more balls = 7 drops

What is in between? The best strategy becomes much harder to find if it is 3-6 balls.

Okay, I'm not sure you'd call this a "general" solution, but I've brute forced it with a spreadsheet. Essentially I'm building solution for x+1 balls, based upon the solution for the number of floors which can be searched for a given number of drops (y) with x balls.

Essentially, the idea is that if you've got x balls and y drops, then your first drop can be 1 floor higher than the solution for x-1 balls and y-1 drops (if it breaks then you implement the x-1, y-1 strategy to find the answer). If it doesn't break, then you drop it again from 1 floor higher than the x-1 balls and y-2 drops answer and so on.... The following is a .csv format copy of the solution for 1 to 20 drops and 1 to 7 balls.

I make no claims about this being optimum (although intuitively it seems to me that it ought to be). Also, there may be some errors, as it's late and I can't be bothered to check my work.

drops,1 ball,2 balls,3 balls,4 balls,5 balls,6 balls,7 balls
1,1,1,1,1,1,1,1
2,2,3,3,3,3,3,3
3,3,6,7,7,7,7,7
4,4,10,14,15,15,15,15
5,5,15,25,30,31,31,31
6,6,21,41,56,62,63,63
7,7,28,63,98,119,126,127
8,8,36,92,162,218,246,254
9,9,45,129,255,381,465,501
10,10,55,175,385,637,847,967
11,11,66,231,561,1023,1485,1815
12,12,78,298,793,1585,2509,3301
13,13,91,377,1092,2379,4095,5811
14,14,105,469,1470,3472,6475,9907
15,15,120,575,1940,4943,9948,16383
16,16,136,696,2516,6884,14892,26332
17,17,153,833,3213,9401,21777,41225
18,18,171,987,4047,12615,31179,63003
19,19,190,1159,5035,16663,43795,94183
20,20,210,1350,6195,21699,60459,137979