Author Topic: Logic Puzzles  (Read 38457 times)

0 Members and 1 Guest are viewing this topic.

Offline Simon

  • Administrator
  • Posts: 3114
    • View Profile
    • Lix
Re: Logic Puzzles
« Reply #180 on: December 28, 2015, 07:52:44 PM »
Very good! This was also Proxima's idea on IRC: With substrings like (red, X, black), we can ignore X and score 1 block boundary here.

Love how you give the basic idea. :-)

-- Simon

Offline geoo

  • Administrator
  • Posts: 1397
    • View Profile
Re: Logic Puzzles
« Reply #181 on: December 28, 2015, 11:25:05 PM »
NaOH and I discussed the cookie puzzle in IRC. For posterity, I'm summarizing the discussion here:

I first found a solution eating 20 cookies. NaOH improved upon that by finding a solution with 21 cookies. I believe that this is optimal, below is the solution and my reasons/proof sketch for why I think it's optimal:

Spoiler (click to show/hide)

Offline Simon

  • Administrator
  • Posts: 3114
    • View Profile
    • Lix
Re: Logic Puzzles
« Reply #182 on: December 28, 2015, 11:38:11 PM »
Yes, very nice writeup with a proof.

<SimonN> we could be a wise guy and eat all 30 cookies. Then, whenever we take 1 from box A and 1 from box B, they satisfy anything
<geoo> yes, very good
<geoo> and we get way more cookies
<SimonN> I don't know if the cultural value of this is higher than NaOH's solution
<SimonN> math doesn't segfault, that's very nice
<SimonN> there is the empty truth and that's it. At best, symbol isn't defined


-- Simon

Offline Simon

  • Administrator
  • Posts: 3114
    • View Profile
    • Lix
Re: Logic Puzzles
« Reply #183 on: January 15, 2019, 04:53:53 AM »
3-5 years ago, I saved this puzzle to a file, intending to post it here here once the then-running puzzles were solved. Shockingly, I've never come around to post it. Here it is!

4 boxes, 4 men

There are four boxes. One contains 3 black balls, the next contains 2 black, 1 white, the next contains 1 black, 2 white, and the final one contains 3 white balls. There are four labels describing the contents, BBB, BBW, BWW, WWW, with each box bearing one of these labels. None of the boxes are correctly labelled.

The boxes are randomly distributed among four men, A, B, C, and D. These men know the setup as described in the above paragraph, but they may only read the label of their own box, and it is not possible to examine balls without taking them out of the boxes.

Now, in alphabetical order, each man is ordered to read their box label (without announcing the label aloud), then take out and examine two balls from their own box, and make a truthful statement.

A says: "I drew two black balls, and I know the color of my third."
B says: "I drew a black and a white, and I too know the color of my third."
C says: "I drew two white balls, but I can't deduce the color of my third from only these two balls and my label." (= C doesn't take any statements by A or B into account.)

D is a blind man, unable to check ball colors or read labels. Thinking hard for a while, he says: "I know the colors of all three balls in my box, and I can tell the color of A's, B's, and C's third balls."

How does he know?

-- Simon
« Last Edit: June 08, 2021, 06:51:59 AM by Simon »

Offline Ramon

  • Posts: 100
    • View Profile
    • JRK Studios
Re: Logic Puzzles
« Reply #184 on: January 15, 2019, 10:37:06 AM »
Spoiler (click to show/hide)

Offline Simon

  • Administrator
  • Posts: 3114
    • View Profile
    • Lix
Re: Logic Puzzles
« Reply #185 on: January 15, 2019, 05:16:32 PM »
Correct answer by Ramon!

Forestidia and I solved it together today, and we stumbled on the same ambiguity in the original puzzle. There are two possible solutions. To fix the ambiguity and force one of the solutions, I've changed in the puzzle:

C: "I drew two white balls." to
C: "I drew two white balls, but I don't know the color of my third." See next post.

Thus, Ramon's answer remains correct, it is now the only correct one.

-- Simon
« Last Edit: January 21, 2019, 11:28:47 PM by Simon »

Offline Simon

  • Administrator
  • Posts: 3114
    • View Profile
    • Lix
Re: Logic Puzzles
« Reply #186 on: January 21, 2019, 11:32:15 PM »
Changed the 4-men-4-balls riddle again: Now, when C announces that he cannot deduce his own 3rd ball, C explicitly doesn't take into account the statements of A and B.

Reason for the change: The puzzle must be solvable from the blind man D's hearing of A's, B's, and C's statements. But if D can deduce everything here, then C must have been able to deduce everything already because C can't learn anything new after making his own statement. It would be inconsistent to let C have all knowledge that D has, yet let only D be able to deduce C's third ball.

Ramon's answer remains the only correct answer.

-- Simon

Offline Simon

  • Administrator
  • Posts: 3114
    • View Profile
    • Lix
Re: Logic Puzzles
« Reply #187 on: June 08, 2021, 06:58:53 AM »
I've found this one but haven't solved it yet. Feel free to post solutions in spoiler tags, but I won't look at any solutions until I've solved it.

Train circle

There is a natural number n > 0 of train cars. The cars form a single big circle: Each car is attached to exactly two other cars, one at the front and one at the back. In each car, the light is either on or off, initially at random.

You're in one of the cars. You can walk back and forth in the circle. In each car that you visit, you can switch the light on or off as you like. Find an algorithm that determines the number n of cars in the circle, in finite time.

-- Simon
« Last Edit: June 08, 2021, 03:42:33 PM by Simon »

Offline Dominator_101

  • Posts: 7
    • View Profile
Re: Logic Puzzles
« Reply #188 on: June 08, 2021, 02:23:51 PM »
Spoiler (click to show/hide)
:P

Okay, here's some real thoughts on the puzzle (not a solution really, but I'll spoiler just in case. It's mostly just kind of brainstorming an issue):
Spoiler (click to show/hide)

Offline geoo

  • Administrator
  • Posts: 1397
    • View Profile
Re: Logic Puzzles
« Reply #189 on: June 08, 2021, 03:06:09 PM »
This is a nice one! Below my proposed solution.

Spoiler (click to show/hide)
« Last Edit: June 08, 2021, 07:44:40 PM by geoo »

Offline Simon

  • Administrator
  • Posts: 3114
    • View Profile
    • Lix
Re: Logic Puzzles
« Reply #190 on: June 08, 2021, 03:41:59 PM »
Dominator has found exactly the problem that makes the task interesting. You're on good track.

geoo posted 2 algorithms in his spoiler tag, his first matches what I found during lunch break. geoo's second one improves the run time over what I found, I didn't think of that. Nice!

Spoiler (click to show/hide)

-- Simon
« Last Edit: June 08, 2021, 08:00:27 PM by Simon »

Offline Dominator_101

  • Posts: 7
    • View Profile
Re: Logic Puzzles
« Reply #191 on: June 08, 2021, 04:10:40 PM »
(unrelated, but I tried the 4 box puzzle that was the previous one for fun, here's my working out if anyone is interested)
Spoiler (click to show/hide)

For the current puzzle, going off Simon's post:
Spoiler (click to show/hide)

Offline Dominator_101

  • Posts: 7
    • View Profile
Re: Logic Puzzles
« Reply #192 on: June 14, 2021, 06:04:23 PM »
Okay, had some more thoughts on this yesterday while trying to sleep, here's my thoughts/findings:

Spoiler (click to show/hide)
« Last Edit: June 14, 2021, 08:09:40 PM by Dominator_101 »

Offline Simon

  • Administrator
  • Posts: 3114
    • View Profile
    • Lix
Re: Logic Puzzles
« Reply #193 on: June 18, 2021, 05:18:37 AM »
Dominator's proof of 4-boxes-3-balls is right, very nice.

Re: Train circle (click to show/hide)

-- Simon

Offline Armani

  • Posts: 223
  • :D
    • View Profile
Re: Logic Puzzles
« Reply #194 on: June 18, 2021, 01:57:15 PM »
The train circle problem reminds me of an old imo problem :) :
https://artofproblemsolving.com/community/c6t304885f6h62190_the_lamp_invariant_game