Solve this equation for me

[Dr Tran]

ethiopia

[Jtehanonymous]

For the glass ball thing I'd get a friend to help. Then I'd have them drop the ball on floor 1 as I dropped it from 10. If neither ball broke then I'd move up to floor 20, and my friend could go to 11. In the worst case scenario I'd go 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, and in these ten actions, my friend would be simultaneously at 91 with me. Then together we'd drop 92 and 93 together, 94 and 95 together, until we got to 98 and 99 together. This would take us 14 drops total working together.

Edit: And I just decided that this sucks because if my ball broke at 90 or something, then we'd only have one ball to go up from 81-89. >=/

The maximum here is still 18 though...

[super kid]

Hahahaha. sorry...

[stargroup]

gg_guru as if I couldn't have any less respect for you

you went and proved me wrong

[GG_Guru]

Umm thanks?

I'm honored?

???

?????

[leonid]

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]

also another math problem:

Prove



using induction.

[MrRubix]

Originally Posted by leonid

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]

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]

Originally Posted by leonid

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]

Damn apparently I thought way too complicatedly on this problem

[Niala]

Originally Posted by MrRubix

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

Only in Soviet Russia. (Had to)

[leonid]

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]

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]

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]

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]

Originally Posted by leonid

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]

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]

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]

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?)