wu :: forums « wu :: forums - Hard-MM2, Egg, Zeno, 7Bool » Welcome, Guest. Please Login or Register. Dec 8th, 2021, 11:06am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: Icarus, towr, Eigenray, SMQ, ThudnBlunder, william wu, Grimbal)    Hard-MM2, Egg, Zeno, 7Bool « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Hard-MM2, Egg, Zeno, 7Bool  (Read 1755 times)
Cze-Jwin
Guest

 Hard-MM2, Egg, Zeno, 7Bool   « on: Jul 25th, 2002, 6:15pm » Quote Modify Remove

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

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...

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.
 IP Logged
Ryan
Guest

 Re: Hard-MM2, Egg, Zeno, 7Bool   « Reply #1 on: Jul 25th, 2002, 10:14pm » Quote Modify Remove

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.
 IP Logged
william wu

Gender:
Posts: 1291
 Re: Hard-MM2, Egg, Zeno, 7Bool   « Reply #2 on: Jul 26th, 2002, 4:54pm » Quote Modify

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.
 IP Logged

[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
Aleksi Liimatainen
Guest

 Re: Hard-MM2, Egg, Zeno, 7Bool   « Reply #3 on: Jul 31st, 2002, 3:37am » Quote Modify Remove

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.
 IP Logged
Eric Yeh
Senior Riddler

Gender:
Posts: 318
 Re: Hard-MM2, Egg, Zeno, 7Bool   « Reply #4 on: Aug 2nd, 2002, 8:15am » Quote Modify

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!
 IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
tim
Junior Member

Posts: 81
 Re: Hard-MM2, Egg, Zeno, 7Bool   « Reply #5 on: Aug 2nd, 2002, 4:22pm » Quote Modify

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
 IP Logged
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »