Logic Puzzles

[geoo]

I haven't really bothered working on any of the problems, but I do have a Clam-style solution to C1:

You don't need to change any weights, since balance is determined by torque not weight.  You can just adjust the fulcrum at each bar to balance the torques. http://www.lemmingsforums.com/Smileys/lemmings/winktounge.gif" alt=";P" title="Wink-Tongue" class="smiley" />

That bears the (easier) question: how many of these do you have to change? http://www.lemmingsforums.com/Smileys/lemmings/tongue.gif" alt=":P" title="Tongue" class="smiley" />

I'm definitely going to take a break on this thread and play around with the SMS custom levels stuff happening in that other thread.  I think most of these problems are probably beyond me (or at least I'd need to go back to my old algorithm textbook to refresh memory on stuff).

Apart from the algorithm for strongly connected components, you don't need any too advanced algorithms, actually. I guess you're familiar with things like the euclidean algorithm, sorting and breadth-first search.
The solutions are simple if you can find the idea, each algorithm can be described in 1-2 sentences.

EDIT: For those interested, there is a detailled solution of problem #5: http://www.cs.rug.nl/~grl/ds05/sumproduct.pdf" class="bbc_link" target="_blank">http://www.cs.rug.nl/~grl/ds05/sumproduct.pdf
A proof to the light bulb problem hasn't been posted yet either, but it's rather easy.

[Simon]

No progress on the open puzzles? Here's three more that geoo already knows.

General notes. These are hat riddles. A hat riddle involves a team of contestants who have to work together, and must decide on a strategy for the quest at hand. They will know the protocol in advance. After agreeing on a strategy, they may not communicate from that point onwards, and everybody will receive a hat in some color determined at random. While each contestant may look at other people's hats, they may not see their own color. Their quest is to name their own hat color. The puzzle itself is to formulate a protocol for the team that ensures a given number of correct guesses.

Hat puzzle 0. Three contestants get either a red or blue hat each. Everybody may see both other persons' hats. Everybody receives a piece of paper and a pen. Simultaneously, i.e. without seeing what everybody else writes down, they must write "red", "blue", or nothing at all. They win if nobody guesses incorrectly, and at least one person has guessed correctly. Find a strategy that ensures a chance of winning greater than 1/2.

Hat puzzle 1. There are countably many contestants, each numbered with a unique natural number. Each gets either a red or blue hat. Everybody may examine the hat color of only one other contestant. He can choose freely which one to examine, and the examined doens't gain any information by this. Simultaneously, everybody must then guess his own color. Find a protocol that ensures infinitely many correct guesses.

Hat puzzle 2. Again, we have countably namy contestants indexed with the natural numbers, and everybody has a red or blue hat, but now every contestant may see all hats of the contestants who have a greater number than himself. Guessing is simultaneous. Find a protocol that ensures only finitely many wrong guesses. Hint: Use the axiom of choice. ;-)

-- Simon

[chaos_defrost]

#0: Easy game: Have each player declare the hat color opposite of what they see iff they see two hats of the same color.

This has a 3/4 chance of a win and a 1/4 chance of everyone being wrong

I'll think about 1 and 2 later

[chaos_defrost]

A logic puzzle I got as part of a timed IQ test on another forum. I think I got it but I'm not 100% sure.

There are six numbers, which can be expressed as the products of two numbers ab, ac, ad, bc, bd, and cd. Five of these products are, in no particular order, 2, 3, 4, 5, and 6. What is the sixth?

[ccexplore]

About 30 minutes after seeing this on the forum, I worked out the answer, but by making a leap in logic I haven't yet been able to close.

12/5 (or 2.4)

I can narrow it down to 5 possible answers only one of which is rational, so that's the one I pick as the answer.  I haven't yet worked out why logically the irrational ones are not actually possible.  (Oh, and talk about unintentional bad puns.).

[chaos_defrost]

Ok, that's what I got too, good.

[ccexplore]

Okay, finally nail down the one and only answer by a slightly different approach, can't believe it took that long. http://www.lemmingsforums.com/Smileys/lemmings/XD.gif" alt=":XD:" title="XD" class="smiley" />

Without loss of generality we'll say that the 4 numbers are A B C and D, and that the missing product not given is C*D.  Then notice that (A*C)/(B*C) = A/B = (A*D)/(B*D).  So of the 5 given numbers, the ratio of one pair of them is equal to the ratio of another pair of them, and then the remaining number must be A*B.  This allows us to quickly narrow it to A*B=5, as 4/2=6/3.  Now notice that (A*C)*(B*C)*(A*D)*(B*D) = (A*B)*(A*B)*(C*D)*(C*D).  So the product of the other 4 numbers, 2*3*4*6, is 5*5*(square of the number we're looking for), and now we can solve the equation to find the number.

[chaos_defrost]

When I got that problem I only had 10 minutes to solve it and three admittedly slightly easier questions: My solution wasn't exactly what you'd call rigorous, but

We know that ab*cd = ac*bd = ad*bc. Of the five given numbers, the only two pairs of two numbers that give the same result if multiplied is 3*4 and 2*6. In order to make the last product the same, we need the number that when multiplied by 5 equals 12, or 12/5.

[ccexplore]

Actually I'd say the logic is perfectly tight and complete as a solution. http://www.lemmingsforums.com/Smileys/lemmings/thumbsup.gif" alt=":thumbsup:" title="Thumbs Up" class="smiley" /> I knew it should be something more direct like that for a logic puzzle, but just drew a blank myself and went a more brute-force way.

[Proxima]

Solution to Simon's hat puzzle #1:

Contestant #1 examines #2, #2 examines #3, #3 examines #1, and all three guess they have the same colour as what they see. At least one must be right. Repeat with every trio of numbers (3n+1 3n+2 3n+3) and you get infinitely many correct guesses

[Simon]

Steve and Proxima are correct with hat puzzles #0 and #1.

I will simply reveal the solution of #2, because it needs a rigorous set theory argument, and even then it's counterintuitive.

Consider the space of functions N -> {red, blue}, called F. The contestants define an equivalence relation ~ on F as follows. Two hat distributions f, g: N -> {red, blue} are equivalent iff there exists a natural number n with f(k) = g(k) for all n >= k. (I.e. the hat distributions differ only on finitely many elements smaller than some n.)

Take the quotient set F/~, i.e. the set of all equivalence classes. By axiom of choice, the contestants agree on a choice function c: F/~ -> F, such that for any class B of equivalent hat distributions, c(B) is a certain distribution in B.

During the actual contest, each contestant determines the equivalence class B of the hat distribution at hand. Ignoring/changing a finite number of hats cannot change the equivalence class of any hat distribution, so each contestant, no matter how far up in the sequence, is able to determine B. Each contestant n now guesses c(B)(n). By definition of ~, only finitely many candidates get it wrong. (The probability of each candidate being right is still 1/2, so you can't turn this into a measure space.)

Product puzzle is nice with a straightforward short solution. I didn't get it in the 10 minutes and got lost in details.

-- Simon

[Simon]

This is a nice one from an older book of mine.

A steam train is travelling between Chicago and New York City. Its staff consists of an engine driver, a stoker, and a conductor. Their names are Miller, Jones, and Babbitt, in no particular order. Three academics are travelling with the train, Dr. Miller, Dr. Jones, and Dr. Babbitt. (I.e. there are six people in total.) We have the following clues:

a) Dr. Babbitt lives in Chicago.
b) Dr. Jones earns exactly $2,500.00 per month.
c) The conductor lives in a town halfway between Chicago and New York City.
d) The conductor's neighbor is one of the passengers and earns exactly 3 times as much per month as the conductor.
e) The academic who shares the conductor's last name lives in New York City.
f) Miller has recently beaten the stoker at chess.

What is the name of the engine driver?

-- Simon

[mobius]

Miller


-Miller can't be the stoker (f).
-Jones is the conductor. Because; Dr. Jones lives in NYC. (e)
     -Dr Miller is the neighbor of the conductor:
        -(Dr Jones's earning: ($2,500)  isn't exactly divisible by 3= can't be neighbor.
        -Dr. Babbit lives in Chicago; not -between there and NY.= can't be neighbor
    -If Dr. Miller is the neighbor then he can't live in NY, we already know Babbit lives in Chicago so Jones is the one living in NYC. (c, e)


I usually figure these puzzles out by making a list and drawing lines. It helps me a lot but then when I go to explain my answer; fail.  http://www.lemmingsforums.com/Smileys/lemmings/XD.gif" alt=":XD:" title="XD" class="smiley" />

[Simon]

Correct answer, and a good explanation!

-- Simon

[Proxima]

Oh no, geoo's Tame 13 video has been stolen! The suspects are a Classic lemming, a Highland lemming and a Shadow lemming, and one and only one of them is guilty. And as we all know, Classic lemmings always tell the truth, Shadow lemmings always lie, and you can't trust a Highland lemming, they can do either (but, if asked a yes/no question, they will always respond one way or the other).

The suspects are close friends, and all of them know who the guilty party is. Furthermore, they may or may not have switched clothes, so you can't tell which of them is which -- let's just refer to the three as A, B and C in the order they're standing, from left to right.

Your task is to find the guilty party (that is, which of A, B, C is guilty, not which tribe) in the fewest number of questions possible. All questions must have "yes" or "no" as the correct answer. Each question must be directed at a particular one of the three; if you ask two (or all three) of them the same question, that counts as two (or three) towards your total.

So, what is the smallest number of questions to do this?