game theory / logic puzzle

[NotJeff]

Originally Posted by TheKeck

Ok, then I guess I would say that there is a book with no words in it. Is that what you're looking for?

That doesn't seem to work, since the question specifies there are more books than there are words in any book. IE, that means there needn't be books with every number of words.

Edit: Derf.

[TheKeck]

Woot, I finally got one without cheating.

[Ink Asylum]

Originally Posted by NotJeff

That doesn't seem to work, since the question specifies there are more books than there are words in any book. IE, that means there needn't be books with every number of words.

Edit: Derf.

Yes there must. If every book as has a unique number of words, than no matter the size of the library it will contain books which have every possible number of words ranging from 0 to X-1, where X is the number of books in the library.

To simplify, if the library has 3 books, then those books must have 0 words, 1 word, and 2 words to satisfy the conditions of the library.

[NotJeff]

Originally Posted by Ink Asylum

Yes there must. If every book as has a unique number of words, than no matter the size of the library it will contain books which have every possible number of words ranging from 0 to X-1, where X is the number of books in the library.

To simplify, if the library has 3 books, then those books must have 0 words, 1 word, and 2 words to satisfy the conditions of the library.

Yeah, my Derf was me figuring that out.

[TheKeck]

All right, if anybody is working on the balance problem, I'll try to outline the horrible answer.

1) Balance 4 vs 4
2a) If they are all the same, balance 2 of the the ones you already have with 2 of the others.
3ai) If they are both the same, balance one of the ones you already have measured vs. one of the last two.
3ai: If the scale is the same, you know the one you never measured is the odd ball. If they are different, you know that new ball you just measured is the odd ball.

3aii) If they are different, balance one of the ones you already measured vs one of the two you just introduced.
3aii: If they are the same you know is was the OTHER of the two you just introduced. If they are different you know it's the one you just tested.

2b) If they are uneven, move three balls from left to right, remove three balls from the right, and introduce three new balls to the left.
2bi) If the scale balances, you know one of the three you just removed is the odd ball. You can also determine whether the odd ball is heavier or lighter now depending on how the scale changed.
3bi) Measure two of the possible odd balls.
3bi: If they are the same, you know the third is the odd ball. If they are different you know which is the oddball because you now know which way the scale should tip.

2bii) If the scale flip flops, you know the odd ball is one of the three that you switched sides. Again, you also can determine whether it is heavier or lighter.
3bii) Again, measure two of the candidate odd balls.
3bii: Use the same logic to find that either the third one is the odd ball, or one of the two you just measured is the odd ball.

2biii) If the scale remains the same, you know one of the two that you left alone is the odd ball.
3biii) Measure one of those two vs. any of the others.
3biii: If they are the same you know, the other is the odd ball, if they are different you know this is the odd ball.


Clear as mud?

Also: I fully recognize that my whole numbering/outline system might be screwed up a bit.

[Reelya]

Originally Posted by TheKeck

Ok. Now can you come up with a method that will work no matter which one the odd ball happens to be?

I also considered the groups of 4 method to get it in 4 measurements. I wasn't sure you could do any better than that, i guess trying groups of 3 to start.

- group into 4 lots of 3 each. Compare the first 2 lots of 3. If they're the same, you know the odd ball is in the other half, and vice versa. 1 measurement reduces the field to 6 balls.

- take one of the discarded groups of 3, and compare to one of the 2 remaining candidate triples. Depending whether they are the same or different, you can discard one of the remaining groups of 3, knocking it down to 3 candidates only.

I can't think of any test which will knock the remaining 3 balls down to 1 in only 1 test though. There would need to be a test that can eliminate more than half the balls in a single test.

[TheKeck]

Originally Posted by Reelya

I also considered the groups of 4 method to get it in 4 measurements. I wasn't sure you could do any better than that, i guess trying groups of 3 to start.

- group into 4 lots of 3 each. Compare the first 2 lots of 3. If they're the same, you know the odd ball is in the other half, and vice versa. 1 measurement reduces the field to 6 balls.

- take one of the discarded groups of 3, and compare to one of the 2 remaining candidate triples. Depending whether they are the same or different, you can discard one of the remaining groups of 3, knocking it down to 3 candidates only.

I can't think of any test which will knock the remaining 3 balls down to 1 in only 1 test though. There would need to be a test that can eliminate more than half the balls in a single test.

Here's some hints, if you want them.

With the method I outlined, you have narrowed it down to at most three balls after the second measurement.

If you have three candidates left after the second measurement, you have ALSO determined whether the odd ball is lighter or heavier.

You start by measuring groups of 4.

[MagGnome]

I was so busy reading this thread that I nearly missed my stop. Darn you guys!

[TheKeck]

Let's say that you have one person sitting on a bus. Concoct a scheme to keep that person from exiting the bus when he means to.

[Ox]

I believe I might have solved the truth machines.

Call the machines A, B, C. Ask A, "Is it true that B works if and only if you use green to mean true?"

If both A and B work and green means true, the statement is true and A will display green. Buy B.
If both A and B work but green means false, the statement is false and A will display green. Buy B.
If A works and B doesn't and green means true, the statement is false and A will display red. Buy C.
If A works and B doesn't and green means false, the statement is true and A will display red. Buy C.
If A is broken it will display a random color, and both B and C work perfectly. Buy B on green and C on red.

[Panthera]

I figured out the truth machines only because of Labyrinth.

[TheKeck]

Originally Posted by Ox

I believe I might have solved the truth machines.

Call the machines A, B, C. Ask A, "Is it true that B works if and only if you use green to mean true?"

If both A and B work and green means true, the statement is true and A will display green. Buy B.
If both A and B work but green means false, the statement is false and A will display green. Buy B.
If A works and B doesn't and green means true, the statement is false and A will display red. Buy C.
If A works and B doesn't and green means false, the statement is true and A will display red. Buy C.
If A is broken it will display a random color, and both B and C work perfectly. Buy B on green and C on red.

Yeah, that was the basic solution I found online.

Originally Posted by Panthera

I figured out the truth machines only because of Labyrinth.

I am well aware of the Labyrinth puzzle, but this one is about 17 levels of complexity beyond that. The fact that you would even equate the two makes me question whether you got the right answer......

[Panthera]

Originally Posted by TheKeck

Yeah, that was the basic solution I found online.

I am well aware of the Labyrinth puzzle, but this one is about 17 levels of complexity beyond that. The fact that you would even equate the two makes me question whether you got the right answer......

It was an important hint. I wouldn't say it's 17 levels of complexity higher - it basically is a matter of generalizing the solution from a two door problem to a three machine problem. I came up with the same answer, not sure I would have known where to start without it.

[TheKeck]

Originally Posted by Panthera

It was an important hint. I wouldn't say it's 17 levels of complexity higher - it basically is a matter of generalizing the solution from a two door problem to a three machine problem. I came up with the same answer, not sure I would have known where to start without it.

So, just to be clear, is your solution basically the same as Ox's solution?

[Panthera]

Originally Posted by TheKeck

So, just to be clear, is your solution basically the same as Ox's solution?

Yes, is that incorrect?

[TheKeck]

Originally Posted by Panthera

Yes, is that incorrect?

Nope, it's right. I guess, just in my mind, the solutions seem radically different. I really see hardly any similarity at all. Good on you for seeing what I couldn't, though.

[Panthera]

On the topic of logic, this is a fun and educational game: http://www.newgrounds.com/portal/view/598731

One caveat, on some displays the drop-down box many not show all the answers, leading to frustration if you don't know to use the down-arrow to scroll.

[MagGnome]

Originally Posted by Panthera

I figured out the truth machines only because of Labyrinth.

Same here!

[Reelya]

Here's a fun one:

There are two types of inhabitants in the world: humans and vampires. Humans always tell the truth and vampires always lie. Also, inhabitants can either be sane or insane. Someone who is insane has all of their beliefs backwards; everything true they believe to be false, and everything false they believe to be true.

For example, if you ask an insane vampire, “Is the sky blue?” he will insanely think that it isn’t and then lie and say that it is. He will answer, “Yes.”

What is a single yes or no question that you could ask to any inhabitant to determine if he is a human or a vampire?

[Panthera]

I'm getting deja vu here.