|
Smart? (pg. 3)
|
View this Thread in Original format
| drizzt81 |
| quote: | Originally posted by AndiH
What's the "worst case"? |
assume that you develop an algorithm that will test for the second floor at the very end. the worst case is the number of times you'd have to iterate to get to floor 2. |
|
|
| Flyboy217 |
| quote: | Originally posted by drizzt81
oops today isn;t my day, i was thinking that i had to DETERMINE the weight of yours.. not balance it..
with a sum of 52 i will be able to tell you how much your weight is :/
still not bad, if that had been teh question :toothless
try 1,3,7,17,31,79 |
I don't follow. If I give you a 100 weight, how can you tell me that it's 100 if your weights sum to 52?
Your 6 weights work, but are suboptimal :-) |
|
|
| Flyboy217 |
| quote: | Originally posted by AndiH
What's the "worst case"? |
The "worst case" depends entirely on your algorithm. For example, if you decided to drop from 1, then 2, then 3, etc... then your worst case would be the 100th floor. It would take 100 tries in the worst case then. You need an algorithm whose worst case is minimal. |
|
|
| AndiH |
| quote: | Originally posted by Flyboy217
The "worst case" depends entirely on your algorithm. For example, if you decided to drop from 1, then 2, then 3, etc... then your worst case would be the 100th floor. It would take 100 tries in the worst case then. You need an algorithm whose worst case is minimal. |
No, in that case my worst case would be 99 since you said that the egg would break if dropped from the 100th floor. Also, now I assume that there's no ground floor? |
|
|
| Flyboy217 |
| quote: | Originally posted by AndiH
No, in that case my worst case would be 99 since you said that the egg would break if dropped from the 100th floor. Also, now I assume that there's no ground floor? |
You are correct, 99 is the worst case, since I've implicitly guaranteed you it will break by 100 (by enforcing that you must actually find N, rather than allowing you to say "it doesn't break from 1-100"). It's a moot point though; it doesn't change the optimal algorithm or final answer.
Not sure what you mean by a "ground floor." The eggs may break from story 1, if that's what you mean. |
|
|
| DigiNut |
| quote: | Originally posted by Flyboy217
I'll go one step further and tell you that you make a faulty assumption in your first sentence. Any more and I'd be telling you the solution. |
Ok, I think I've figured it out.
You drop the first egg at the 15th floor. If it breaks, you count up in sequence from 1 to 13 (14 drops).
Then you drop the next egg at the 29th floor. If it breaks, count up in sequence from 16 to 28 (again 14 total).
Keep going up to the 42nd, 54th, 65th, 75th, 84th, 92nd, and 99th floors, which gives you intervals of 11, 10, 9, 8, 7, etc. respectively, all with a total worst-case drop of 14.
So the worst case is 14.
Right?
I'd hardly call this an "elegant" solution though... it's not elegant unless you know it in advance. |
|
|
| DigiNut |
I still think there's something wrong with your question 3. The cups are in arbitrary positions, and the "genie" can rotate them at an arbitrary angle, and you're saying there's a way to guarantee getting them all face up?
There has to be something in this question that's not random, aside from your instructions. That is, unless we're talking about a Gaussian system and assuming an infinite number of "rounds"... |
|
|
| Flyboy217 |
| quote: | Originally posted by DigiNut
Ok, I think I've figured it out.
You drop the first egg at the 15th floor. If it breaks, you count up in sequence from 1 to 13 (14 drops).
Then you drop the next egg at the 29th floor. If it breaks, count up in sequence from 16 to 28 (again 14 total).
Keep going up to the 42nd, 54th, 65th, 75th, 84th, 92nd, and 99th floors, which gives you intervals of 11, 10, 9, 8, 7, etc. respectively, all with a total worst-case drop of 14.
So the worst case is 14.
Right?
I'd hardly call this an "elegant" solution though... it's not elegant unless you know it in advance. |
The worst case is indeed 14, but your solution is slightly flawed. Suppose the eggs break at 15. Then you try 15, find the egg breaks, and try 1-13 and it doesn't. You don't know whether the answer is 14 or 15 now. Instead, your first drop should be 14.
It extends nicely so that an M-story building requires N drops such that N(N-1)/2 = M. The fun part is understanding that your drops must decrease to balance out the worst case. Most people wrongly believe it must be constant. I sadly removed that joy for you :-P |
|
|
| starglider |
When I'm in the mood for extra math homework, I'll find you.
Until then... I'll just wait for Acid Junkie to have a go. ;) |
|
|
| Flyboy217 |
| quote: | Originally posted by DigiNut
I still think there's something wrong with your question 3. The cups are in arbitrary positions, and the "genie" can rotate them at an arbitrary angle, and you're saying there's a way to guarantee getting them all face up?
There has to be something in this question that's not random, aside from your instructions. That is, unless we're talking about a Gaussian system and assuming an infinite number of "rounds"... |
It is solvable as stated. Feel free to assume an unbounded number of rounds if you like, but please don't try to argue that a random solution will eventually work; it's not *guaranteed* to win.
P.S. I love your pseudo-math terminology. "Real integral" number systems in the "2+2=5" thread. "Directional unit vectors" while trying to explain an n-dimensional space. All that's required of the vectors is that they're linearly independent-- they certainly don't need to be unit, and "directional" is meaningless in this context.
It sounds like you're trying to impress TAs, so I won't burst your bubble. I suppose for the most part, it seems to be working ;-) |
|
|
| Abject Silver |
i direct your attention to 'writing against your life' by richard mitchell, better known as the grammarian.
i love math just as much as the next guy, but uhh.... well, just read it, especially you intellects. you know who you are. it'll kick your asses to infinity and back before you can say 'MENSA!!!' |
|
|
| Flyboy217 |
| quote: | Originally posted by Abject Silver
i direct your attention to 'writing against your life' by richard mitchell, better known as the grammarian.
i love math just as much as the next guy, but uhh.... well, just read it, especially you intellects. you know who you are. it'll kick your asses to infinity and back before you can say 'MENSA!!!' |
I couldn't find this title on Amazon. Is it an older book? What's it about?
And I love the way people associate Mensa with "genius." There are societies with *much* higher intelligence requirements (Triple Nine, Iquadrivium) for truly brilliant people :-) |
|
|
|
|
