|
||
|
Title: Hard-MM2, Egg, Zeno, 7Bool Post by Cze-Jwin on Jul 25th, 2002, 6:15pm mastermind 2 = yellow, yellow, yellow, light blue Egg Dropping... what if you took number of floors /2... if the egg breaks at 50 than start at 1? if the egg doesnt break start from 50? so max number would be (num_floors/2)-1 Zeno's Paradox it sounds like...the dist needed to catch up 1/10,1/11,1/12,1/13,1/14, etc...and u would never reach 0 is that a correct assumption? perhaps i read the problem wrong... so i guess he can never catch up? 7Boolean ok..tell me if this logic is wrong... so if i do a binary search type deal... i would start by asking.. assuming that the person answers correct all the time... 1. is the number greater or equal to 7 2. is the number greater or equal to 11 3. is the number greater or equal to 13 4. is the number greater or equal to 14 5. is the number 14 6. is the number 15 so max number i would need to ask would be 6 questions.. to check to see if the person lied..u do the next logical question in that series....so for example...if he lied in #2 and the answer really is 15 than i would purposely ask #3 to see if he lied... this is of course assuming that he cant lie if i guess the correct number. |
||
|
Title: Re: Hard-MM2, Egg, Zeno, 7Bool Post by Ryan on Jul 25th, 2002, 10:14pm The thing about Zeno's paradox (which is really one of many that Zeno created) is that it requires time to be constantly slowed and slowed. It is always told in terms of where the tortoise WAS...not in terms of how fast either of them are moving. Neither's speed is dependent on the speed or position of the other. Simply consider Achilles moving at 10m/s and the tortoise at 1m/s. After 2 seconds, Achilles is 20m ahead of his starting position and the tortoise is 2m ahead of its starting position. They don't have to be racing one another, moving in the same direction, or even moving at the same time. |
||
|
Title: Re: Hard-MM2, Egg, Zeno, 7Bool Post by william wu on Jul 26th, 2002, 4:54pm You can do better than (num_floors/2) - 1. I noticed you jumped by 50 floors on the first step. Try jumping in smaller intervals. It's kind of amazing -- if you had only one egg, then clearly the upper bound running time is 100 drops. So it seems logical that 2 eggs should cut that time in half. But actually you can chop the maximum running time down to 14 drops. Regarding the 7 boolean questions solution, your method of detecting lies doesn't always work -- in some cases, you'll need all 7 questions. Where the lie is inserted affects how many steps you'll need to take. I'd like to write more but computer lab is closing ... gotta go. |
||
|
Title: Re: Hard-MM2, Egg, Zeno, 7Bool Post by Aleksi Liimatainen on Jul 31st, 2002, 3:37am I think I've figured out a solution to the 7bool question. Here's the reasoning I used: We need to find out the number, and then check if there are any errors in it, which means we'll need 4 bits for the number and we have 3 bits left for error correction. Now we'll need a scheme which will let us identify the location of the error (if any) and figure out the corrupted part from what we know to be intact. One way to do this would be to compute checksums of 3 bits to determine which triplet may be corrupted and then use the other checksums to find the correct ones. Here is my solution: All questions are about the binary representation of the number, with digits numbered from 0 (least significant) to 3 (most significant). The number (data): -Is digit 0 1? -Is digit 1 1? -Is digit 2 1? -Is digit 3 1? Error correction (checksum questions): -Is the sum of digits 1, 2 and 3 even? -Is the sum of digits 0, 2 and 3 even? -Is the sum of digits 0, 1 and 3 even? If a checksum disagrees with the values of the digits we know that one of those four answers must be incorrect. The other answers must then be correct, and we can figure out the rest from those. More precisely: -If all checksums match, there is no error. -If one checksum is wrong, that checksum is incorrect. -If two checksums are wrong, the bit that is included in those but not in the correct one is incorrect. -If all checksums are wrong, the bit included in all three is incorrect. |
||
|
Title: Re: Hard-MM2, Egg, Zeno, 7Bool Post by Eric Yeh on Aug 2nd, 2002, 8:15am Yep, I had the same answer for 7 Booleans: ask for each bit and xor in three triples. Does anyone have a more elegant solution? In any case, it's a pretty nice result that the amount of information is optimal for the precisely 7 bits of information being transferred (4 bits of number plus 3 bits for the precisely eight possible lying outcomes). I expected there to be a little more wasted data transfer but I was pleasantly surprised! |
||
|
Title: Re: Hard-MM2, Egg, Zeno, 7Bool Post by tim on Aug 2nd, 2002, 4:22pm Once you think of the problem as getting 4 bits of information with one possible error to be corrected, it's pretty clear how to find a solution :) |
||
|
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |