The Ball-Drop Problem - Solve w/o Knowing the Solution!

PMH · 2020-07-20 01:18:50

The solution to the Ball-Drop Problem begins with the answer, and relies on it throughout. Although it's nice to see that, that's kinda cheating!

I'd like to see a simple (as possible) solution that doesn't require knowing the answer first!

(72 years old, BS in Pure Math from MIIT)

Bob · 2020-07-20 04:04:52

hi PMH

Welcome to the forum.

I see that puzzle was provided by JaneFairfax. She hasn't been active on the forum for a long time now, but, in her day, she was a formidable brain. And she expected her readers to follow her arguments with the same level of genius. Not always possible for us mere mortals!

I think there is some logic there but half the steps are missing (Probably she thought they were obvious ).

Let's say you try the nth floor and it's the best. If a ball breaks you can test from 1 to n-1 in that order to establish the level.

If the ball doesn't break you need to try a higher floor in a similar way. No good trying a number equal to n + another n, because if the ball breaks it will now take another n-1 to find the level so, on top of the two tries you have already had that means n + 1 tries. But I wanted n to be the maximum number. So I'll try n + one less than n this time.

If it breaks I still have n-2 tries to find the level, so n altogether again.

If it doesn't break then by a similar logic I'll try n-2 higher and so on.

I can stop if I reach floor 99, because, if I haven't yet found the level, it must be floor 100.

So I'm looking for n, such that n + (n-1) + (n-2) + (n-3) + ..... comes to 99. Note: this sequence doesn't have to end in +3 + 2 +1. It can end sooner, provided I reach 99.

At this stage you can use trial and improvement (a spreadsheet helps) to home in on n = 14 quite quickly. [There may be an algebraic way to get 14 with any trialling. I'll try that now and post again if I find a way.]

Bob

PMH · 2020-07-20 06:19:39

Thank you so much!

The seemingly obvious "try n+1" was new to me - and so, appreciated, even though it's not algebraic.

Yes, I'm wanting an algebraic solution.

Sadly, although I've found two in the past, trying for several days hasn't reproduced them - so I'm feeling old and useless.

Bob · 2020-07-20 20:17:47

RE_WRITE of post.

You will see from the next post by Phrontister that I made a careless mistake and said that 9 was a prime. I've realised that the solution doesn't need primes anyway so here's a complete revision.

We need:

Clearly b - a < b + a + 1 and this pair must be a whole number factor pair multiplyig to give 198, so the possibilities are:

1 x 198, 2 x 99, 3 x 66, 6 x 33, 9 x 22, 11 x 18.

So I'll investigate b - a being each of the first of these pairs:

If b - a = 1, then a = 98 and b = 99

If b - a = 2, then a = 48 and b = 50

If b - a = 3, then a = 31 and b = 34

If b - a = 6, then a = 13 and b = 19

If b - a = 9, then a = 6 and b = 15

If b - a = 11, then a = 3 and b = 14.

You will notice that b gets smaller as b - a gets larger.

This follows because to make b smallest we want b + a + 1 to be smallest, and that will happen when b - a is largest.

So I could have left out all those trials and jumped straight to b - a = 11 immediately.

I'm feeling old and useless.

That's why joining MIF was a good move. We'll have you back to your prime in no time.

Bob

phrontister · 2020-07-21 12:24:21

Hi Bob;

I was just quickly scanning recent posts, and spotted this:

bob bundy wrote:

198 has 4 prime factors, 1, 2, 9, and 11.

According to my understanding of primes, 198 has 3 prime factors: 2, 3 and 11.

I didn't look to see if this makes any difference to your work there.

Last edited by phrontister (2020-07-21 13:17:34)

Bob · 2020-07-21 19:35:51

hi Phro,

Whoops! I feel like such a fool. I was so pleased I'd found a method, I overlooked this detail. Which is easier: rework the whole of maths defining 9 to be a prime, or change my earlier post?

Think I'll make the edit.

Thanks,

Bob

PMH · 2020-07-22 00:04:04

off-topic - but since I'm here:

How do you make the nice math characters that are in your first reply?

I used to be able to do them in Word, but never in a context like this one.

Bob · 2020-07-22 01:22:06

hi PMH,

Apologies for thinking 9 is a prime. Still it doesn't alter the proof. I'm wondering whether to make it a bit neater now I've finished developing it.

Also sorry that I've taken so long to reply. I had forgotten I was still logged in from earlier so I've only just spotted your reply.

The maths characters are done using a code called LaTex. The FluxBB engine that drives the forum will jump to the interpreter when it meets the command open square bracket math close square bracket. The interpreter switches off again in a similar way with the command /math

There's a tutorial here: http://www.mathisfunforum.com/viewtopic.php?id=4397

The first 20 or so posts will be enough to get you started. Then you can dip in when you need a specific symbol.

Also useful: http://latex.codecogs.com/legacy/eqneditor/editor.php

You can create code there to copy and paste into your post.

Furthermore, if you see some LaTex that you want to investigate, just click on it to see how it was done.

Other square bracket type commands you might find useful:

quote url hide img b (for bold) u (for underline)

Hope that helps,

Bob

PMH · 2020-07-22 06:10:01

Thanks!

Don't worry about taking finite time to reply!

PMH · 2020-07-22 06:24:40

In the LaTex tutorial, the exaample code should be in plain text -- but it's already been interpreted. (so you can't tell what to type to get the result)

Is there a switch for that that should be used on that page?

Bob · 2020-07-22 09:25:43

hi

There was a command square brackets code that allowed a poster to show their line of LaTex code completely without activating the interpreter. I don't know why that doesn't now work. But I've found a way round it. I've deliberately left out a close bracket. Then the code command shows the rest so you just have to re-insert the missing bracket.

Here's the first example using that trick.

[math V_{sphere}=\frac{4}{3}\pi r^3[/math]

But there's an easy way to see what the code is.

In the first example I clicked on the LaTex and got this: V_{sphere}=\frac{4}{3}\pi r^3

You can always do this to see what the code was.

I've decided to re-write post 4 properly in case anyone else is misled by it.

Bob

PMH · 2020-07-23 00:13:01

Thanks.

Yes, I agree that we should end up with a nice clean solution.

And it'd be nice to connect it up to the old problem statement, somehow.

PMH · 2020-07-28 00:51:52

Looking over your solution again (Page 4), I realized that I don't, in fact, understand where the summation equation comes from. Would you please explain?

PMH · 2020-07-28 01:00:19

I've been working on an approach to presenting a solution that tries to make each step simple and easily held in the mind. It starts like this:

Let F be the number of floors, and k be the number of the floor that it's optimal to drop the first ball from.

Drop a ball from the kth floor
(We don't know what the value of k is yet; it's an unknown with only the property that we've set for it (it's the optimal first-drop floor).)

If the ball doesn't break, we still have two balls - and only F-k floors to cover.
(We've dropped a ball once so far.)
If it does break, we have k-1 floors left to test, with only one ball left to test them with.
And the only way to do that is to start at the bottom floor and test each floor above that successively until either it breaks or we get to the (k-1)th floor (we've tested the kth floor)
(We could just continue on up testing with the second ball - but testing only one floor at a time is not efficient enough for the optimal solution.)

State: 2 balls, F-k floors to test.

We'll climb up a few floors to do our next test drop -- but how many?
If we go up too much farther, we won't be able to test all the remaining floors below that with a single surviving ball - which violates a condition of our effort.

Bob · 2020-07-28 19:59:49

hi PMH,

In my solution I got to the point where I wanted

b + (b-1) + (b-2) + ... + (a+3) + (a+2) + (a+1) = 99

If sum(n) means the sum of the natural numbers up to n then my formula can be re-written as

sum(b) - sum(a)

There's a formula for the sum of n natural numbers which can be worked out as follows:

sum(n) = n + (n-1) + (n-2) + ... + 3 + 2 + 1

sum(n) = 1 + 2 + 3 + ... + (n-2) + (n-1) + n

adding

2 x sum(n) = (n+1) + (n+1) + (n+1) + .... + (n+1) + (n+1) + (n+1) = n x (n+1)

so

Bob

PMH · 2020-07-29 01:51:05

continuing (finishing) my previous:

We're testing in blocks, in effect.
:
o 0-k1
o k1+1 - k1+k2
, etc.
Once we've finished the first block, we know that floors 1-k are no-break - and so that the break floor occurs above there. We're into the second block. k2 is analogous to k1 in its block.
But where, exactly, is k2?
We have now dropped one ball, so we can't take as many drops for this block as we did for the first - so let's try just one less.
Go up one from k1, and test the block from there to F, using no more than k-1 drops.
k2 = k1 + 1
This generates the series k1, k1+1, k1+2, ...
which has to sum to F.
Sum: k*(k+1)/2 + k*k*(k+1)/2
= (k+1)*(k+1)/2
so F = (k+1)^2/2
so k = sqrt(2F)

Bob · 2020-07-29 20:13:28

hi PMH

Go up one from k1, and test the block from there to F, using no more than k-1 drops.
k2 = k1 + 1

Shouldn't that be k2 = k1 -1 ?

This generates the series k1, k1+1, k1+2, ...
which has to sum to F.
Sum: k*(k+1)/2 + k*k*(k+1)/2
= (k+1)*(k+1)/2
so F = (k+1)^2/2
so k = sqrt(2F)

I think that is Sum = k(k+1)^2 over 2

Bob

Math Is Fun Forum

#1 2020-07-20 01:18:50

The Ball-Drop Problem - Solve w/o Knowing the Solution!

#2 2020-07-20 04:04:52

Re: The Ball-Drop Problem - Solve w/o Knowing the Solution!

#3 2020-07-20 06:19:39

Re: The Ball-Drop Problem - Solve w/o Knowing the Solution!

#4 2020-07-20 20:17:47

Re: The Ball-Drop Problem - Solve w/o Knowing the Solution!

#5 2020-07-21 12:24:21

Re: The Ball-Drop Problem - Solve w/o Knowing the Solution!

#6 2020-07-21 19:35:51

Re: The Ball-Drop Problem - Solve w/o Knowing the Solution!

#7 2020-07-22 00:04:04

Re: The Ball-Drop Problem - Solve w/o Knowing the Solution!

#8 2020-07-22 01:22:06

Re: The Ball-Drop Problem - Solve w/o Knowing the Solution!

#9 2020-07-22 06:10:01

Re: The Ball-Drop Problem - Solve w/o Knowing the Solution!

#10 2020-07-22 06:24:40

Re: The Ball-Drop Problem - Solve w/o Knowing the Solution!

#11 2020-07-22 09:25:43

Re: The Ball-Drop Problem - Solve w/o Knowing the Solution!

#12 2020-07-23 00:13:01

Re: The Ball-Drop Problem - Solve w/o Knowing the Solution!

#13 2020-07-28 00:51:52

Re: The Ball-Drop Problem - Solve w/o Knowing the Solution!

#14 2020-07-28 01:00:19

Re: The Ball-Drop Problem - Solve w/o Knowing the Solution!

#15 2020-07-28 19:59:49

Re: The Ball-Drop Problem - Solve w/o Knowing the Solution!

#16 2020-07-29 01:51:05

Re: The Ball-Drop Problem - Solve w/o Knowing the Solution!

#17 2020-07-29 20:13:28

Re: The Ball-Drop Problem - Solve w/o Knowing the Solution!

Board footer