Solve this equation for me

[leonid]

Re: Solve this equation for me

I wasn't able to solve this problem within 15 minutes how dumb =/

Is fourteen the optimal expected number of drops? Just to check whether I'm on the right track..

edit: nvm

[stargroup]

Re: Solve this equation for me

also another math problem:

Prove



using induction.

[MrRubix]

Re: Solve this equation for me

I wasn't able to solve this problem within 15 minutes how dumb =/

Is fourteen the optimal expected number of drops? Just to check whether I'm on the right track..

edit: nvm

Yes

[leonid]

Re: Solve this equation for me

Does this work?

Let x be the bottom floor of current searching space.
Divide current searching space into seven and drop the ball from the top of the bottommost divided area. Call it floor y.
If it breaks, drop the second ball through floor x to floor y-1.
If it doesn't break, set the searching space from y+1 to 100 and repeat the process.

Begin by setting searching space from floor 1 to 100

[MrRubix]

Re: Solve this equation for me

Does this work?

Let x be the bottom floor of current searching space.
Divide current searching space into seven and drop the ball from the first divided area. Call it floor y.
If it breaks, drop the second ball through floor x to floor y.
If it doesn't break, set the searching space from y+1 to 100 and repeat the process.

A better way to think of it: Why not shorten your search spaces with each new interval? If you drop first at 14, then you know you only need to drop 1-13 if it broke at 14. But if it doesn't break at 14, drop at 14 + (14-1) = 27, and if it breaks, then you drop from 15 to 26 for a worse case scenario, here, of 2 + 12 = also 14...

The idea is that you are locking things into a worst-case drop of 14 no matter how many intervals you go up -- for each wasted "first-sphere drop" you expend with the interval search, you compensate by simply making the search space smaller for the second sphere.

Why 14? Because the sum from 1-14 is when you first break 100.

You're starting at 14 and working your way down... by the time you reach the end of the process, you've gone through all possible floors.

[leonid]

Re: Solve this equation for me

Damn apparently I thought way too complicatedly on this problem

[Niala]

Re: Solve this equation for me

You do not prepare for the Putnam -- the Putnam prepares YOU

Only in Soviet Russia. (Had to)

[leonid]

Re: Solve this equation for me

BTW, that algorithm I stated should probably work. Except that I had to calculate the expected number of drops with computer >_> so I wouldn't be able to get it right on the interview.


I'll work on that red/black deck problem.. Looks fun and awfully difficult.

I've always wanted to be a good problem solver, but I'm still not there x(

[MrRubix]

Re: Solve this equation for me

The algorithm seems okay btw, but I'm not confident in it because I don't understand how you derived it -- I personally just go for the "compensation logic" approach and finding the first top-floor-breaking 1-through-X sum.

[MrRubix]

Re: Solve this equation for me

Interested to know how you came about the div-7 logic in your algorithm... that seems really interesting to me.

I mean, like, 100/7 = roughly 14, so drop at 14. Say it doesn't break. So you drop at 14+(100-14)/7 = 26 (versus my 27)?

[leonid]

Re: Solve this equation for me

I haven't thoroughly tested edge cases. Could be 26 (if you get floor(14+(100-14)/7)) or 27 (if you get ceiling(14+(100-14)/7)).

I just went through div-2 to div-20 or something, calculating the expected value in floating number form, and div-7 happened to have smallest such value.

So yeah it required me a computer -_-

[MrRubix]

Re: Solve this equation for me

I haven't thoroughly tested edge cases. Could be 26 (if you get floor(14+(100-14)/7)) or 27 (if you get ceiling(14+(100-14)/7)).

I just went through div-2 to div-20 or something, calculating the expected value in floating number form, and div-7 happened to have smallest such value.

So yeah it required me a computer -_-

The problem I had is that even when I applied floors/ceilings, I ended up with, for the very first case for instance: ceiling(0+(100-0)/7) = 15, when a floor here would yield 14, but a floor would yield 26 in the next case and a 27 with a ceiling.

[MrRubix]

Re: Solve this equation for me

Also for floor versus ceiling scenarios:

14 15
26 27
36 37
45 46
52 53
58 59
64 64
69 69
73 73
76 76
79 79
82 82
84 84
86 86
88 88
89 89
90 90
91 91
92 92
93 93
94 94
94 94
94 94
94 94
94 94
94 94
94 94
94 94

Unless I am misunderstanding your algo lol

[leonid]

Re: Solve this equation for me

Looks like treating integers as real numbers caused a disaster -_-

I'll conclude that this algorithm works only if we have infinite number of floors **** (of course the optimal solution won't be div-7 in this case)

[MrRubix]

Re: Solve this equation for me

Do you mean "continuous floors" as opposed to discrete ones? lol


Reminds me of that one movie... can't remember the name of it. The one where there's like a Floor 7.5 or something (Being John Malkovich?)