Author Topic: Logic Puzzles  (Read 75467 times)

0 Members and 1 Guest are viewing this topic.

Offline geoo

  • Administrator
  • Posts: 1473
    • View Profile
Re: Logic Puzzles
« Reply #90 on: August 04, 2011, 07:44:59 AM »
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. ;P
That bears the (easier) question: how many of these do you have to change? :P

Quote
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
A proof to the light bulb problem hasn't been posted yet either, but it's rather easy.

Offline Simon

  • Administrator
  • Posts: 3860
    • View Profile
    • Lix
Re: Logic Puzzles
« Reply #91 on: October 01, 2011, 01:54:54 AM »
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

Offline chaos_defrost

  • Posts: 908
  • the artist formerly known as Insane Steve
    • View Profile
Re: Logic Puzzles
« Reply #92 on: November 06, 2011, 04:06:48 AM »
#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
"こんなげーむにまじになっちゃってどうするの"

~"Beat" Takeshi Kitano

Offline chaos_defrost

  • Posts: 908
  • the artist formerly known as Insane Steve
    • View Profile
Re: Logic Puzzles
« Reply #93 on: September 01, 2012, 02:28:24 AM »
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?
"こんなげーむにまじになっちゃってどうするの"

~"Beat" Takeshi Kitano

Offline ccexplore

  • Posts: 5311
    • View Profile
Re: Logic Puzzles
« Reply #94 on: September 01, 2012, 05:39:26 AM »
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.

Quote from: answer
12/5 (or 2.4)

Quote from: what I haven't proved logically
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.).

Offline chaos_defrost

  • Posts: 908
  • the artist formerly known as Insane Steve
    • View Profile
Re: Logic Puzzles
« Reply #95 on: September 01, 2012, 05:47:05 AM »
Ok, that's what I got too, good.
"こんなげーむにまじになっちゃってどうするの"

~"Beat" Takeshi Kitano

Offline ccexplore

  • Posts: 5311
    • View Profile
Re: Logic Puzzles
« Reply #96 on: September 01, 2012, 06:13:50 AM »
Okay, finally nail down the one and only answer by a slightly different approach, can't believe it took that long. :XD:

Quote from: complete answer
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.

Offline chaos_defrost

  • Posts: 908
  • the artist formerly known as Insane Steve
    • View Profile
Re: Logic Puzzles
« Reply #97 on: September 01, 2012, 06:33:50 AM »
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

Quote from: answer
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.
"こんなげーむにまじになっちゃってどうするの"

~"Beat" Takeshi Kitano

Offline ccexplore

  • Posts: 5311
    • View Profile
Re: Logic Puzzles
« Reply #98 on: September 01, 2012, 07:18:14 AM »
Actually I'd say the logic is perfectly tight and complete as a solution. :thumbsup: 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.

Online Proxima

  • Posts: 4562
    • View Profile
Re: Logic Puzzles
« Reply #99 on: September 01, 2012, 12:01:29 PM »
Solution to Simon's hat puzzle #1:

Quote
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

Offline Simon

  • Administrator
  • Posts: 3860
    • View Profile
    • Lix
Re: Logic Puzzles
« Reply #100 on: September 01, 2012, 01:18:57 PM »
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.
Quote
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

Offline Simon

  • Administrator
  • Posts: 3860
    • View Profile
    • Lix
Re: Logic Puzzles
« Reply #101 on: September 01, 2012, 11:42:38 PM »
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

Offline mobius

  • Posts: 2747
  • relax.
    • View Profile
Re: Logic Puzzles
« Reply #102 on: September 02, 2012, 12:49:02 AM »
Quote

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.  :XD:
everything by me: https://www.lemmingsforums.net/index.php?topic=5982.msg96035#msg96035

"Not knowing how near the truth is, we seek it far away."
-Hakuin Ekaku

"I have seen a heap of trouble in my life, and most of it has never come to pass" - Mark Twain


Offline Simon

  • Administrator
  • Posts: 3860
    • View Profile
    • Lix
Re: Logic Puzzles
« Reply #103 on: September 02, 2012, 01:21:37 AM »
Correct answer, and a good explanation!

-- Simon

Online Proxima

  • Posts: 4562
    • View Profile
Re: Logic Puzzles
« Reply #104 on: September 02, 2012, 02:00:51 AM »
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?