Logic Puzzles

[chaos_defrost]

Yea, those are what I also got. For the other two, I'm trying to map a function to the number of vertices (we know f(4) and f(http://www.lemmingsforums.com/Smileys/lemmings/cool.gif" alt="8)" title="Cool" class="smiley" /> - the octahedron is a special case as each vertex has four paths) but it's proving a bit tricky: Especially since a theoretical f(6) can have a couple of different probabilities depending on how the space is mapped.

A couple more ant probability problems, these of my design (at least I haven't seen them elsewhere).

I) You place two ants on opposite corners of a square. Each ant randomly moves to an adjacent corner along a side at the same time. If the ants hit the same corner or cross paths they explode, if not they will again move to an adjacent corner along a side at the same time, again exploding if they cross. What is the probability the ants will eventually switch places from their original positions without exploding?
II) Same scenario as I, only now the ants start on opposite angles of a hexagon.
III) Same scenario as I and II, only now the ants start on opposite vertices of a regular octahedron.

I admittedly have not obtained a "100% sure" answer to 3, but am working on it.

[Simon]

I'd do it with a Markoff chain, which is easy for the square, but gets large for the other shapes. Is there a trick that saves work? (Except just identifying equivalent states in the chain.)

-- Simon

[chaos_defrost]

If you decide you can rotate or mirror the octahedron, and re-label which ant is ant A and which is ant B, there's really only six states of nature: both ants on starting vertices, both ants on center square, one edge apart, both ants on center square on opposite corners, one ant on starting vertex one in center, one ant on opposite starting vertex one in center, and both ants on opposite starting vertices (the desired state). The reason I don't quite have an answer is that some of the possible loops are a bit tricky to close up, which I wasn't quite expecting when I posited the question.

EDIT: Alright I have a "close approximate" answer, I'm not sure how feasible an exact answer is but I have it within, say, .01%

EDIT2: I should elaborate, in my problems use of a calculator is ok

[Proxima]

I have an answer for the square:

First, assume that after an explosion, the ants keep moving, so that after n moves there will always be 4^n equally probable move sequences.

The probability of success after 2 moves is 1/8 (2 out of 16 sequences -- they could move either way round the square).

The probability of success in exactly 4 moves is 1/64 (4 out of 256 -- the first ant must backtrack on move 2, so there are two choices for which way it moves first, two choices for which way it goes round on moves 3 and 4. The second ant never has any choice, as it must always avoid the first ant.)

Similarly, the probability of success in exactly 6 moves is 1/512, and in 2n moves is 1/8^n, so the overall probability of success is the sum of the powers of 1/8, which is of course 1/7.

[chaos_defrost]

Yea, square looks good.

Hexagon is deceptively tricky:

There's a few too many different states of nature to run a Markov chain unless you just want to compute it with a program, but note that most of the states aren't ever reachable from the current state.

I do have an exact fractional answer for the hexagon, since there's a way to do it without explicitly using Markov chains (sort of)

[Simon]

I have found this variant of the 15-puzzle: http://homepages.cwi.nl/~tromp/oriscript4.html" class="bbc_link" target="_blank">http://homepages.cwi.nl/~tromp/oriscript4.html and you need to enable Javascript.

Rules: You are the white box, and in each step, you can switch places with a neighboring piece (use cursor keys). Purple pieces may only be entered/switched vertically, and the green pieces, horizontally. The object is to move the labelled green piece to the left column.

-- Simon

[chaos_defrost]

Neat puzzle. I took 62 moves the first time I solved it but that's probably not optimal. It could be really interesting if larger grids are used.

Answers for the harder shapes in the exploding ant problem:

Hexagon:

There are two important things to this one:

1) Vertically mirrored positions on the hexagon, if you align it so the starting corners are on top and bottom, are probabilistically equivalent.
2) After any move, the ants are ever only on opposite corners, or they are on corners connected by an edge. I will call a situation where the ants are on opposite corners "open" and on where they are on connecting corners "closed".

The ants start in an open position, and are both three corners from their goal. I will refer to this position as "open-3", or O3. If we consider mirrored states to be equal to each other in terms of how far the ants are from the goal state, there are three other open positions, "open-2," "open-1," and "open 0," which I will call O2, O1, and O0. O0 is our goal state.

From any open state, the ants have a 50% chance of moving to a new open state, and a 50% chance of moving to a closed state. If the ants move to an open state, they will be a different number of spaces away from the goal, with a 50/50 chance of moving in either direction. So, if the ants are in state O3, they can only move to O2, but if they are in O2 or O1, they have can move to a closer or farther open state with equal probability.

If the ants are in a closed state, the next move there is a 25% chance they will explode, a 50% chance they will move to a new closed state, and a 25% chance they will move to an open state. Since the ants can only move to one possible open state, and the desired state is open, I will denote each closed state with the number of the open state the ants will be in if they move to it. Thus, we have "closed-3," "closed-2," "closed-1," and "closed-0," or C3, C2, C1, and CO. A move where the ants move from an open state to a closed state will keep the number of the state the same. If they move to a new closed state, it will, like the open states, shift in either direction with equal probability. So, if the ants are in C3 and move to a new closed state, it can only be C2, if they are in C0, they can only move to C1, and either of the others can shift either way with equal probability.

The odds that an ants eventually reaches the desired state O0 before an explosion is equal to the sum of the probabilities of reaching it from the states it can go to times the probabilities of going to those states. The ants can only ever reach the goal state from O1 or C0, but it is possible to set up a system of 7 equations in 7 variables (a simplified Markov Chain, if you will) to show the possible movements. In these equations, the variables are the probabilities of reaching O0 before exploding from each state:

C0 = 1/4 + 1/2C1
C1 = 1/4O1 + 1/4C0 + 1/4C2
C2 = 1/4O2 + 1/4C1 + 1/4C3
C3 = 1/4O3 + 1/2C2
O1 = 1/4 + 1/2C1 + 1/4O2
O2 = 1/4O1 + 1/2C2 + 1/4O3
O3 = 1/2O2 + 1/2C3

It can be done by hand (although it's kind of tedious, I used a system of equations solver), but if you solve for O3 you get 183/1126.

For the octahedron:

I'd just go with a Markov chain here. The trick is noticing that, while there's a LOT of orientations of the ants, there's really only seven different states of nature possible if you describe them in general terms:

1) Explosion
2) Ants on opposite vertices (desired state)
3) Ants on starting vertices
4) Ants on adjacent corners of the center square of the octahedron (align it so the starting vertices are on the top and bottom)
5) Ants on opposite corners of the starting square
6) One ant on starting vertex, the other on a center vertex
7) One ant on opposite vertex, the other on a center vertex

This can be best modeled with a Markov chain, and is a special kind where all paths eventually reach either of state one or two. The state matrix is:

[1 0 0 0 0 0 0]
[0 1 0 0 0 0 0]
[1/4 0 0 1/2 1/4 0 0]
[3/16 1/16/ 1/16 3/16 0 1/4 1/4]
[1/4 1/16 1/16 0 1/8 1/4 1/4]
[3/16 0 0 1/4 1/8 1/4 3/16]
[3/16 0 0 1/4 1/8 3/16 1/4]

I won't go into the computations too much, but the probability of ending in state 2 starting in state 3 is about 10.37%

[Minim]

Interesting puzzle, and it's not too frustrating either. http://www.lemmingsforums.com/Smileys/lemmings/smiley.gif" alt=":)" title="Smiley" class="smiley" /> That kind of puzzle reminds me of Rush Hour, where the cars and trucks had to be moved in a certain way and you had to get the red car off the board.

[Simon]

Here's another cute logic puzzle. The site I got it from offers a solution, thus no link yet.

The task is to answer the following five questions correctly. Each comes with one correct and three false possible answers.

Q1. What is the lowest-numbered question with B as correct answer? A) Q1, B) Q4, C) Q3, or D) Q2.
Q2. What is the answer to question Q4? A) answer D, B) answer A, C) answer B, or D) answer C.
Q3. What is the answer to question Q1? A) answer D, B) answer C, C) answer B, or D) answer A.
Q4. How many questions have D as their correct answer? A) three, B) two, C) one, or D) none.
Q5. How many questions have B as their correct answer? A) none, B) two, C) three, or D) one.

The same site regularly runs quizzes with psychological contests, e.g. "From the numbers 1 through 100, choose a number. You win if you choose the lowest number which no other participant has chosen." Others call for most popular answers similar to Family Feud, e.g., name a dinosaur which as many other participants as possible will also name. I feel inclined to run a couple of such questions on the Lemmings Forums, getting answers via PM, and revealing the results after 3-6 days. Are people interested in such things? (Name a useless L2 skill other than Diver *grin*)

-- Simon

[ccexplore]

The same site regularly runs quizzes with psychological contests, e.g. "From the numbers 1 through 100, choose a number. You win if you choose the lowest number which no other participant has chosen." Others call for most popular answers similar to Family Feud, e.g., name a dinosaur which as many other participants as possible will also name. I feel inclined to run a couple of such questions on the Lemmings Forums, getting answers via PM, and revealing the results after 3-6 days. Are people interested in such things? (Name a useless L2 skill other than Diver *grin*)

Sounds fun, I'm interested.

[Proxima]

The task is to answer the following five questions correctly. Each comes with one correct and three false possible answers.

Q1. What is the lowest-numbered question with B as correct answer? A) Q1, B) Q4, C) Q3, or D) Q2.
Q2. What is the answer to question Q4? A) answer D, B) answer A, C) answer B, or D) answer C.
Q3. What is the answer to question Q1? A) answer D, B) answer C, C) answer B, or D) answer A.
Q4. How many questions have D as their correct answer? A) three, B) two, C) one, or D) none.
Q5. How many questions have B as their correct answer? A) none, B) two, C) three, or D) one.

First, neither A nor B can be the correct answer to Q1 without an obvious absurdity.

If D is the answer, then B is the answer to Q2, so A is the answer to Q4. That means D must be the answer to Q1, Q3 and Q5, but D being the answer to Q3 contradicts D being the answer to Q1.

Therefore, C is the answer to Q1, B is the answer to Q3, and the answer to Q2 is not B, so the answer to Q4 is not A. If it's B then we have a similar problem: D must be the answer to Q2 and Q5, but D being the answer to Q2 contradicts C being the answer to Q4.

Therefore, C is the answer to Q4 (it obviously cannot be D), which makes D the answer to Q2. This means no other question can have D as correct answer. Just one question so far has B as correct answer, so the answer to Q5 must be B or D, but it cannot be B.

This gives us the full solution: Q1 - C; Q2 - D; Q3 - B; Q4 - C; Q5 - B.

[Simon]

Right!

-- Simon

[chaos_defrost]

So on the puzzle competition board http://thesuicidalrodents.proboards.com/index.cgi" class="bbc_link" target="_blank">here I posted a few puzzles from a competition I want to host on another site somewhere. There's one more with a question on it posted there. I'd be very appreciative if some people gave it a go.

(If you don't have access to the puzzle group boards on that site let me know and I'll give it to you; you need this access to view the thread with the puzzles.)

[Proxima]

I have found this variant of the 15-puzzle: http://homepages.cwi.nl/~tromp/oriscript4.html" class="bbc_link" target="_blank">http://homepages.cwi.nl/~tromp/oriscript4.html and you need to enable Javascript.

Rules: You are the white box, and in each step, you can switch places with a neighboring piece (use cursor keys). Purple pieces may only be entered/switched vertically, and the green pieces, horizontally. The object is to move the labelled green piece to the left column.

Got it in 40. I think this is the best that can be done.

[chaos_defrost]

I saw a site a little while ago which has one of my personal favorite "humans are wired really oddly" puzzles on it and want to share. There are two parts.

1) You work an incredibly exciting job doing quality control work for a factory that produces board games. There is one rule to the cards that are created for the game:

"If a card has a circle on the front, it MUST have a yellow back."

You have the following four cards in front of you, all of which have a shape of some sort on one side and a color on the other. What card(s) must you flip over in order to make sure the rule is followed? Also, only flip the card(s) you have to flip. Inefficiency will not be tolerated.

http://img.photobucket.com/albums/v495/insanesteve/cards1_zps0b950860.png" alt="" class="bbc_img" />

2) So you get board checking cards for the bored game and take a new job as a bartender. This bar also has one rule, which you may be pretty familiar with:

"If a person orders an alcoholic drink, they MUST be at least 21 years of age."

It's a bit slow at your bar and there's currently only four people there. They are represented below with cards. One one side is the drink that the person has ordered, and on the other side is the person's age. What "card(s)" must you "flip" in order to make absolutely sure that the rule is followed? Again, only flip the card(s) you have to.

http://img.photobucket.com/albums/v495/insanesteve/cards2_zpsd994227a.png" alt="" class="bbc_img" />

Got that? Let's see how you did.

On the shape/color question, I'm pretty sure you flipped the card with a circle on it. Yea, that's one of them: You need to know if that circle card has a yellow back or not. You may have flipped the yellow card, also. That.... was a mistake. You actually have to flip the red card, and not the yellow one.

In layterms, the reason you have to flip the red card is to make sure that it doesn't have a circle on it. As for the other two cards, obviously the rule doesn't apply to cards with squares, so you can ignore that card. The rule also does not say that cards with yellow backs have to have circles on them. A square card with a yellow back does not break the rule.

In logical terms, flipping a card tests one of the four variations of the conditional statement of the rule. The circle card tests the original conditional, the square card tests its inverse (if not p, than not q), the yellow card tests its converse (if q, then p), and the red cards tests its contrapositive (if not q, then not p). In order to test whether the statement is true in all cases, you have to test the original statement and its contrapositive. You cannot deduce anything about the truth of a statement's converse or inverse from the original statement, except that either both are true or both are false.

If you missed that, don't worry. Less than 1/4th the population gets this question right.

As for the drinking question, you have to check the beer drinker to see if he's at least 21, and the 18 year old to see if he's not drinking an alcoholic drink. Here's what interests me about this problem:

1) Almost 60% of the population gets this problem correct, but
2) These two questions ask EXACTLY the same thing, just with different wordings.

As a species, humans are apparently really bad at tasks like this. However, for some reason when we apply rules like this to social settings (such as needing to be 21 to buy liquor), our minds re-wire themselves somehow to be able to do this task. More people will get the first problem wrong and the second right than will get both right, and they are the same question.

I get the feeling this forum will have a much higher than average success rate, but I'm curious.