Logic Puzzles

[ccexplore]

I don't know yet if it's smallest number of questions, but it will find the guilty party.

I can do it in 5 questions.

Start by asking each of them the same question, something like "is 1+1=2?" whose answer is "yes" if answered truthfully.  Classic and Shadow must answer differently, and with 3 lemmings and only 2 possible answers (yes/no), 2 of the lemmings must answer the same way and other lemming different.  Highland cannot be the one who gave the different answer, since that would've meant Classic and Shadow gave the same answer.  So this means the lemming who gave the different answer cannot be Highland, and then based on the answer given, you can determine whether he's Classic (always truthful) or Shadow (always lying).

Now you're just two questions ("is A guilty?", "is B guilty?", both directed at the different-answer lemming from above) away from the guilty party.

[chaos_defrost]

I can definitely do it in one fewer but I don't quite think it's optimal yet:

There are 18 possible states of nature: the 6 orders of the three Lemmings and which Lemming, in line, did it.

Determining who the Highland Lemming is is essential to us (so we can avoid asking him questions about who did it), so we need to ask a question that is integral to this. Ask the center Lemming if the Lemming on the left's tribe name is earlier alphabetically than the one to the right.

If he answers "yes": If he is the Classic Lemming, then Left is Highland and Right is Shadow. If he is Highland Lemming is this one, then we'd be OK asking either of the others about the thief. If he's the Shadow Lemming, then Left is also Highland and right is Classic. So, we direct future questions to the right Lemming.
If "no", the opposite situation happens, and no matter who's in the middle, the left Lemming is safe to ask. We've also narrowed the possible number of states of nature to 12.

getting to it with 3 more questions is easy: ask a factual question and then ask about 2 of the Lemmings if they did it, but I think 3 questions might be possible. Give me a second.

EDIT: Got it down once again

Ask the definite not Highland: "If I asked the other Lemming that is either Classic or Shadow if you are guilty, will they say "yes"?"

If yes, not guilty
If no, guilty

Now ask the definite not Highland: "Can the other two Lemmings possibly both answer "yes" to the question 'is the center Lemming guilty?'"

CHgS - no
CHSg - yes
CSgH - no
CSHg - yes

SCgH - no
SCHg - yes
SHgC - no
SHCg - yes

so if you get a "yes" the right Lemming is guilty, and if you get a "no" the center one is. If you got a "no" on question 2, the left is guilty.

I think I did this right, I think?

[Proxima]

Full marks  http://www.lemmingsforums.com/Smileys/lemmings/thumbsup.gif" alt=":thumbsup:" title="Thumbs Up" class="smiley" />

[Simon]

I don't want to read the spoiler yet. Questions about it:

Does the final answer use 3 questions? Does it identify either Classic or Shadow as an intermediate goal? If so, how many questions to this goal and how many afterwards?

-- Simon

[mobius]

this one came out of a I.Q. Test book. I don't remember how much time you got for it though.

refer to the picture attached

You can only make the machine move by turning cog A. In its current state; it won't move. Ignoring torque problems;
-Without removing any cogs, reposition 3 cogs to make a working circuit where all the cogs turn by turning A clockwise. (they all must be touching at least 1 other cog).

(you can either describe it or edit the picture if you're feeling creative)
There were at quite a few other questions on the same problem but I can't remember them right now I have to find the book. (like; which direction will k turn...)

[Proxima]

I'm not sure I understand what's being asked. The problem with the machine is that it has a cycle (BCDEGIH) of odd length. Adjacent cogs turn opposite directions, so any cycle must be of even length. Seems to me like all you need do is move I elsewhere so G and H can touch.

Re Simon's questions about my problem:

3 is correct. Your second question is a little ambiguous, but if you meant "do you have to identify one lemming as being certainly non-Highland?" then yes. And there are three possibilities for the guilty party, so you can't distinguish them with a single yes/no question, so you must have two left.

[GuyPerfect]

It's possible to identify the guilty Lemming in 2 questions. It's not guaranteed, but the question in Proxima's post asks how few it can be done in, and the answer is 2:

It's impossible to identify the Highland Lemming with just one question, so at least two questions need to be asked.

Let's say that the following exchange takes place:

Speaking to Lemming A:
  Q: Are you the guilty Classic Lemming?
  A: Yes
  Q: Is True the same as False?
  A: No

The only possible circumstances that could produce this outcome would be if Lemming A is the Classic Lemming and is guilty.

[ccexplore]

Um, if I understand correctly the Highland lemming can answer however way he wants, so how does your exchange above rule him out?

[Proxima]

Yes, my question was ambiguous. In problems like this, it's generally assumed (unless stated otherwise) that you're allowed to give a strategy in which subsequent questions vary depending on earlier answers; so the number of questions asked may vary. That makes it unclear whether you're trying to minimise the maximum, the minimum or the expected value (assuming the 18 possibilities for arrangement and guilt are equally probable).

Insane Steve's solution already has the least possible for all three values (and yes, the minimum is 2). Your solution doesn't work for the reason ccexplore stated. (In case it wasn't clear, the Highland lemming can choose whether to lie or tell the truth for each answer separately).

[GuyPerfect]

(In case it wasn't clear, the Highland lemming can choose whether to lie or tell the truth for each answer separately).

You're right. It wasn't clear. It looks to me like you said the exact opposite:

(but, if asked a yes/no question, they will always respond one way or the other).

The way that looks to me is this: in response to yes/no questions, a Highland Lemming will either always answer yes or always answer no.

[chaos_defrost]

Somewhat easier yes/no puzzle I found somewhere:

I am thinking of an integer between 1-9 inclusive. You are allowed to ask me any two yes or no questions to figure out my number, which I will truthfully answer yes or no to. I will also not say anything if you ask a question I can't actually answer truthfully.

Give a system that finds my number every time.

[chaos_defrost]

Also double post for something else I found:

http://puzzle.cisra.com.au/" class="bbc_link" target="_blank">http://puzzle.cisra.com.au/ -- here's a site that runs a puzzle contest every year, and this year's contest looks like it's going to start any day now: though most of the questions look like they are going to be presented the week of the 1st of October.

I'd definitely be up for making a team if there's three other people here interested in these kinds of puzzles. Given that we aren't Australian students we wouldn't be eligible for prizes but it might still be fun.

[Simon]

Solution to Steve's yes-no puzzle:

Need to gain a trit (ternary information) with each question, so we must use possible silence in return to the questions. Generate random information somehow, and keep it hidden; e.g. flip a coin secretly.

First question is "Is the number in {1, 2, 3}, or is it in {4, 5, 6} and did I flip heads?", with "and" binding stronger than "or". Use a similar second question to weed out the number from the appropriate group of three.

-- Simon

[chaos_defrost]

That works, yes.  http://www.lemmingsforums.com/Smileys/lemmings/laugh.gif" alt=":D" title="Laugh" class="smiley" /> My solution was a bit different but similar in idea:

Ask as the first question "I am also thinking of a number; it is either 3.5 or 6.5. Is your number larger than mine?" If the number is in {1,2,3} you'd get a no, if it is in {7,8,9} you get a yes, and if it is in {4,5,6} you get no response. Ask a similar 2nd question to distinguish between the three in the proper set.

[Simon]

I've known "12 balls, weigh 3 times" since high school, but never went into it in detail since it seemed tedious, but also never read a solution since it's a beautiful puzzle. I've finally done it on my own today. No new information here, except that I'm doing a different second weighing in case I) a) than geoo.

12 balls, one is either lighter or heavier than all others.
Use a scale three times to determine which ball has what exact quality.

We call a ball "normal" if it is certainly not the single odd ball.
We call a ball "red" if it is either normal or heavier than the normal balls.
We call a ball "blue" if it is either normal or lighter than the normal balls.

Weighing I:
    Put 4 balls on each side.

Case I a: Both sides are equal.
    We now have 8 normal balls and 4 unknown ones.

    Weighing I a II:
        Put 3 unknown balls on one side, and 3 normal balls on the other.

    Case I a II a: Both sides are equal.
        We now have 11 normal balls and 1 unknown one. Weigh the unknown ball
        against any single normal one for the end result.

    Case I a II b: The 3 unknown balls are heavier than the 3 normal ones.
        Weigh one of the red balls against another red ball to see which of
        the 3 red balls is heavy.

    Case I a II c: The 3 unknown balls are lighter than the 3 normal ones.
        Weigh one of the blue balls against another blue ball to see which of
        the 3 blue balls is light.

Case I b: One set of 4 balls is heavier than the other.
    We now have 4 red balls, 4 blue ones, and know for sure that the unweighed
    4 balls are normal.

    Weighing I b II:
        Left side: 2 red, 2 blue
        Right side: 1 blue, 3 normal

    Case I b II a: Both sides are equal.
        All balls from weighing II must now be normal.
        We have 2 red balls and 1 blue ball remaining from weighing I which
        were not part of weighing II. Weigh the 2 red balls against each other.
        If one is heavier, it's the odd ball, otherwise the blue ball is light.

    Case I b II b: The left side is heavier.
        The red balls from the left side stay red, all other red balls become
        known as normal. Weigh the 2 red balls against each other. If one is
        heavier, it's the odd ball. If they are equal, then the single blue
        ball from the right side of weighing II must be light.

    Case I b II c: The left side is lighter.
        Weigh the two blue balls from the left side against each other to see
        which is the light ball.

New weighing puzzle:

You have 2 black balls, 2 grey balls, 2 white balls. Among each color, one ball is heavier than the second. The three light balls are all of the exact same weight, as are the three heavy balls.

Your task to label each ball as heavy or light. You may use an ordinary balance scale (telling which side is heavier, if any) a total of two times.

-- Simon