Logic Puzzles

[Simon]

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

[geoo]

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

NaOH's solution:
10
12
4, 14, 14
6, 6, 16
8

Optimality sketch:
(1) It's pointless to have one box with all cookies of the same number of chocolate chips: leaving only one cookie of that kind would not affect the probabilities.
(2) A box with one cookie cannot be adjacent to a box with two cookies: imagine X has 1 cookie, Y has 2 cookies, Z an arbitrary number of cookies. Both cookies of Y each must have more chocolate chips than the cookie in X. Assume the cookies in Y have a and b chips, a <= b. Then changing b to a is still a valid solution because Z still trumps Y. But by (1) we can then remove one of the cookies, thus the solution wasn't optimal. The same argument works if Z has 1 cookie, Y 2 cookies, X arbitrarily many.
(3) A sequence of two (or more) consecutive boxes all containing only one cookie each can be collapsed into a single box: Removing (all but) one of the two (or more) boxes still leaves a cycle of non-transitive boxes.
(4) There are at least two boxes with more than 1 cookie: Otherwise, we have a sequence of number of cookies of 1, 1, 1, 1, n that can by (3) be collapsed into a sequence 1, n. However two dice/boxes cannot be non-transitive.
(5) So we must have at least 2 boxes with 2 or more cookies. If there are exactly two such boxes, then by (2) these two boxes must have at least 3 cookies, for a total of 9. With 3 or more such boxes we exceed the total of 9 cookies as the only valid sets of cookie numbers (partition of 9 into 5 parts) would be 1, 2, 2, 2, 2 or 1, 1, 2, 2, 3, neither of which works by (2) and (3).

[Simon]

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

[Simon]

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

[Ramon]

Spoiler

A drew two black balls, so he must have the BBB or BBW box. Since he knows the color of the third ball, his box is labeled as one of those two possibilities and the third ball has the opposite color than what's on the label.

Similarly, B has the BBW or BWW box with one of the respective opposite labels. From the information so far, we can already rule out 2 of the 4 possibilities: (BBW,BBW) and (BBB,BWW), as the same label would otherwise have to be used for both.

C too drew two white balls, but makes no statement about his knowledge of the third ball. He must have the BWW or WWW box. In the following part I will assume that C not mentioning he knows the color of his third ball means he doesn't know it, else my solution would not be unambiguous.

If C had the BWW box, that leaves B with BBW and A with BBB. The corresponding labels would be A:(bbw), B:(bww), C:(www). However with the (www) label C would know the color of his third ball, so we rule it out.

Thus C has the WWW box, now let's look at the labels of boxes A and B, for which there are two possibilities (we previously ruled two of them out).

a) (BBW,BWW) labeled as (bbb,bbw). Thus C must be labeled (bww). In this case however C would know the color of his third ball, so we can rule it out yet again.
b) (BBB,BBW) labeled as (bbw,bww). Thus C must be labeled (bbb).

The last case fulfills all the assumptions made so far and is the conclusion I have come to:

A has (BBB) labeled (bbw)
B has (BBW) labeled (bww)
C has (WWW) labeled (bbb)

Therefore D can conclude without looking at his box or its label that he must have the BWW box with the www label.

[Simon]

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

[Simon]

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

[Simon]

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

[Dominator_101]

Spoiler

Leave your shoes in the first car, proceed through the cars sans-shoe, and when you get your shoe back that's how many cars

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

So, one thing I'm not sure of here is how to actually CONFIRM you've gone around. Even if you did something like always turn all the lights to off, can you really be sure you've done a full loop? Maybe there just happens to be a run of x trains all with their lights off that happen to appear after the point you think you've looped, so even by doing what you think is a second loop maybe you didn't actually do a second loop.

The only thought I have to deal with this so far is you need to do another loop in the opposite direction where you change something and confirm that you are able to observe said change. This seems inefficient, though, although would still be linear time since it's just another cycle of n, but the question is then if you do an extra cycle to confirm the size, but find out that you're wrong, what does that do to the time complexity? Is there a way to keep going still in linear time?

[geoo]

This is a nice one! Below my proposed solution.

Spoiler

For i from 1 to infinity:
- Remember the status of the wagon you start in
- Move ahead by i wagons, and flip the switch of the i-th wagon
- Go back i wagons so you're back at the start. If the light has changed, then you're done (n=i).

This takes O(n^2)

We can make this O(n log n) O(n) but O(n) space if instead we go to the 2^i-th wagon in each iteration, and we log the full sequence of lights we encounter, not just the starting one.
If on the way back something has changed, we know we've made a full loop and we can infer n from the position of the light that has changed.

I don't know if there's a linear time solution.

EDIT: After reading Simon's notes, I realized my math is wrong and this is in fact O(n) and not O(n log n) time: Sum_i=1^k 2^i = 2^k+1-1, and k ~ log n.
Together with Simon's trick to turn off the lights along the way this makes for a linear time, constant space solution, which sounds optimal.

[Simon]

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

You can remove the extra space complexity from the second algorithm: You don't have to log a sequence of lights in a separate list; instead, turn off all lights on the way forward. Turn on light i. Check which car on the way back has lights on.

I don't believe the task is solvable in linear time. geoo showed that walking 2^k wagons is already linear time; this is the amortized linear time that std::vector<T>::push_back must strive for by specification, and it achieves that by reallocating every 2^k times or, in other implementations, every 1.5^k times.

Walking longer won't improve it

Edit: This section here, I wrote it when I assumed that geoo's second algorithm ran in O(n log(n)) time.

I believe the task is solvable in O(n log(log(log(...(log(n))...)) for any number of chained logs. Let f be a function N -> N that grows super fast with k < log(log(...(log(f(k))). Instead of going 2^k wagons on the k-th iteration as geoo suggested, we instead go f(k) wagons on the k-th iteration. Otherwise, the algorithm is the same: Turn off the light on the way forward, turn on the light in car f(k), and see how many cars you have to go back to reach one with light on.

The downside of this theoretical improvement is that the algorithm becomes really slow for common numbers of n that you expect. You don't want to walk through 1,000,000 cars before you see on the way back that there are 19 cars in the loop.

The 2^k-idea sounds like a very good choice, it's also when std::vector reallocates, but I don't know the theory behind this design.

-- Simon

[Dominator_101]

(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

(labels in caps, contents in lowercase)
Who can have what label:
A: bb
   BBB - Know third is w
   BBW - Know third is b
   BWW - can't know third because it's already wrong
   WWW - can't know third because it's already wrong

B: bw
   BBB - can't know third because it's already wrong
   BBW - Know third is w
   BWW - Know third is b
   WWW - can't know third because it's already wrong

C: ww
   BBB - Could be
   BBW - Could be
   BWW - Can't be because he would know the third
   WWW - Can't be because he would know the third

D: Label must be WWW because no one else's can be

B must be labeled BWW because he's the only one who can have that, so his third is b.

Because B has bbw contents, A must have bbb contents, so his label is BBW. This leaves label BBB for C

Labels:
A: BBW
B: BWW
C: BBB
D: WWW

Either C or D must have www as the contents, but D can't have that because that's his label. So C has www. This leaves bww for D's contents

Contents:
A: bbb
B: bbw
C: www
D: bww

For the current puzzle, going off Simon's post:

Spoiler

To avoid the 'walking a million cars to find out there's 19' problem, you could always say that if you hit a series of x cars with lights off that matches the number of cars you already walked through (or maybe bump it to 2x or something for safety, since if car 19 was already off you'd turn around after 18x2 instead of 19x2), you could just turn around at that point, though that doesn't exactly fall neatly into a time complexity.

I'm trying to decide if you did turn a light on and walk back to start, if you con't find a light on on the way back (meaning you didn't loop yet), if it would be helpful to proceed in the other direction or not. Probably not since you still wouldn't really know when you hit the light you turned on, so might as well continue the same direction you already were, knowing you can probably proceed to at the very least 2y cars (where y is the car you decided to turn around in the first time) before you would reach the point where you might've looped.

All in all, not sure if these are even helpful, just trying to throw some ideas out.

[Dominator_101]

Okay, had some more thoughts on this yesterday while trying to sleep, here's my thoughts/findings:

Spoiler

So, I mused in my previous post about whether or not it would be more efficient to change directions every time you returned to the starting car, and after more thinking/exploration I determined that it is, it's actually MUCH more efficient to change directions every time you return to the starting room. Here's the basic idea (also, I'm generally going to use right and left to refer to the directions because it just made the most sense to me to think about it that way):

So if every time you re-traverse the train you always start going right, all those steps you take to get back to the last car you checked are all wasted. You already know the entire path to that train car, so you aren't gathering any new information. However, if you change from right to left every time you return to the first car you can actually gather some information on the trip back out. If I start going right, don't find the end, but then go left instead, I now get to see the two cars to the left of start, which is new information. Then, when I don't find it on the left and head back right, even while traversing back to the furthest car I'm still gathering information, as I might've actually changed a light on that side now.

I'm not sure if I explained that well enough but here's some data I gathered on the total amount of steps that it takes to confirm the car numbers to prove that it's actually a lot more efficient:

Spoiler

Only moving one way:
Only Right, Case 1 : 2 steps
Only Right, Case 2 : 6 steps
Only Right, Case 3 : 12 steps
Only Right, Case 4 : 20 steps
Only Right, Case 5 : 30 steps
Only Right, Case 6 : 42 steps
Only Right, Case 7 : 56 steps
Only Right, Case 8 : 72 steps
Only Right, Case 9 : 90 steps
Only Right, Case 10 : 110 steps
Only Right, Case 11 : 132 steps
Only Right, Case 12 : 156 steps
Only Right, Case 13 : 182 steps
Only Right, Case 14 : 210 steps
Only Right, Case 15 : 240 steps
Only Right, Case 16 : 272 steps
Only Right, Case 17 : 306 steps
Only Right, Case 18 : 342 steps
Only Right, Case 19 : 380 steps
Only Right, Case 20 : 420 steps

Switching directions:
Left/Right, Case 1 : 2 steps
Left/Right, Case 2 : 6 steps
Left/Right, Case 3 : 7 steps
Left/Right, Case 4 : 13 steps
Left/Right, Case 5 : 14 steps
Left/Right, Case 6 : 22 steps
Left/Right, Case 7 : 23 steps
Left/Right, Case 8 : 33 steps
Left/Right, Case 9 : 34 steps
Left/Right, Case 10 : 46 steps
Left/Right, Case 11 : 47 steps
Left/Right, Case 12 : 61 steps
Left/Right, Case 13 : 62 steps
Left/Right, Case 14 : 78 steps
Left/Right, Case 15 : 79 steps
Left/Right, Case 16 : 97 steps
Left/Right, Case 17 : 98 steps
Left/Right, Case 18 : 118 steps
Left/Right, Case 19 : 119 steps
Left/Right, Case 20 : 141 steps

Only moving one direction will always take Σ2n (0 to n) steps to 'solve', whereas changing directions takes...Okay, so, I'm not really sure to be honest. Maybe someone better at math can determine that. The nice thing, though, is that for odd number n the number of steps to 'solve' will always just be the number of steps to solve n-1, plus 1 (because as soon as you enter the next car you will have noticed it changed)

EDIT: Looked into the numbers a little bit, best approximation I can find for the number of steps for each is this (I think):
Σi (for i=1 to n/2) + (3n/2) + 1 (or +2 for odd numbers)
(n/2 is floored for odd numbers as well)
I don't really understand the pattern but...I think this should be accurate?

I also made a quick python script for testing this, for anyone curious. Feel free to check my work/modify the search functions/judge my coding:

Spoiler

Code Select Expand

#!/usr/bin/python
import random

######################
#  Search Functions  #
######################

# Traverse the train always starting to the right
def forwardSearch(train):
totalSteps = 0
stepsToTake = 0
startingLight = train[0]
# Break at 100 in case I'm bad at coding
while stepsToTake < 100:
stepsToTake += 1
# Move to the last car
totalSteps += stepsToTake
# Change the light
train[stepsToTake%len(train)] = not train[stepsToTake%len(train)]
# Walk back to starting car
totalSteps += stepsToTake
# Check the light
if train[0] != startingLight:
# We changed the first car, we know how many cars
return (stepsToTake, totalSteps)

# Traverse the train both left and right
def swingSearch(train):
totalSteps = 0
stepsToTake = 0
startingLight = train[0]
observedRight = []
observedLeft = []
polarity = -1
# Break at 100 in case I'm bad at coding
while stepsToTake < 100:
stepsToTake += 1
polarity *= -1
lights = observedRight if polarity > 0 else observedLeft
# Walk the car
for i in range(1, stepsToTake+1):
totalSteps += 1
curLight = train[polarity * i%len(train)] # Don't access imaginary cars
if i > len(lights):
lights.append(curLight)
elif curLight != lights[i-1]:
# Light changed, log
return (i + stepsToTake-1, totalSteps)
# Change the last light, as well as our observed version
lastCar = polarity * stepsToTake%len(train)
train[lastCar] = not train[lastCar]
lights[stepsToTake-1] = not lights[stepsToTake-1]
# Walk back to starting car
totalSteps += stepsToTake
# Check the light
if train[0] != startingLight:
# We changed the starting car, we know how many cars
return (stepsToTake, totalSteps)

################
#  Run Trials  #
################
def makeTrain(size):
train = []
for i in range(0, size):
train.append(random.randint(0,1) == 1)
return train

NUM_TIRALS = 20
for i in range(1, NUM_TIRALS+1):
# Make a train
train = makeTrain(i)
# One direction search
guess = forwardSearch(train)
if guess[0] == i:
print 'Only Right, Case', guess[0], ':', guess[1], 'steps'
else:
print '!!! BAD ANSWER !!!'
# Switch direction search
guess = swingSearch(train)
if guess[0] == i:
print 'Left/Right, Case', guess[0], ':', guess[1], 'steps'
else:
print '!!! BAD ANSWER !!!'

(EDIT: apologies, it doesn't seem to like my code in a spoiler tag)

I assume this same theory should work for the more complex ways of traversing the train as well, I just did the simple case because it was the easiest.

[Simon]

Dominator's proof of 4-boxes-3-balls is right, very nice.

Re: Train circle

Right, by alternating left and right, you're adding the chance (I believe a guarantee even?) that you run into the switched-on light of your previous iteration whenever that previous iteration made it further than halfway around the circle. Since we travel 2^k wagons forward on the k-th iteration, cutting short the final iteration is a considerable save.

Good find! The complexity remains constant space, linear time, but the factor of the linear time improves.

-- Simon

[Armani]

The train circle problem reminds me of an old imo problem :
https://artofproblemsolving.com/community/c6t304885f6h62190_the_lamp_invariant_game