Puzzles to puzzle you

[Ashutosh]

Imagine you are an ant sitting on the face of a Rubik's cube (http://en.wikipedia.org/wiki/Rubik%27s_Cube) made of cheese. You have been assigned the following task: Eat the whole cube by starting with any subcube on the face. Once you're done with a given subcube, you can move to another subcube which shares a face with the one you just finished. The catch is this: The subcube at the center of the Rubik's cube must be the last subcube eaten.

So the puzzle is: Can you do it?

[Ashutosh]

Here's another tantalizing puzzle (Source: Terence Tao's blog (http://terrytao.wordpress.com/2008/02/05/the-blue-eyed-islanders-puzzle/))

There is an island upon which a tribe resides. The tribe consists of 1000 people, with various eye colours. Yet, their religion forbids them to know their own eye color, or even to discuss the topic; thus, each resident can (and does) see the eye colors of all other residents, but has no way of discovering his or her own (there are no reflective surfaces). If a tribesperson does discover his or her own eye color, then their religion compels them to commit ritual suicide at noon the following day in the village square for all to witness. All the tribespeople are highly logical and devout, and they all know that each other is also highly logical and devout (and they all know that they all know that each other is highly logical and devout, and so forth).

For the purposes of this logic puzzle, "highly logical" means that any conclusion that can logically deduced from the information and observations available to an islander, will automatically be known to that islander.

Of the 1000 islanders, it turns out that 100 of them have blue eyes and 900 of them have brown eyes, although the islanders are not initially aware of these statistics (each of them can of course only see 999 of the 1000 tribespeople).

One day, a blue-eyed foreigner visits to the island and wins the complete trust of the tribe.

One evening, he addresses the entire tribe to thank them for their hospitality.

However, not knowing the customs, the foreigner makes the mistake of mentioning eye color in his address, remarking “how unusual it is to see another blue-eyed person like myself in this region of the world”.

What effect, if anything, does this faux pas have on the tribe? Choose among these two (Do support your answer with a reason):

Effect 1. The foreigner has no effect, because his comments do not tell the tribe anything that they do not already know (everyone in the tribe can already see that there are several blue-eyed people in their tribe).

Effect 2. 100 days after the address, all the blue eyed people commit suicide :omg:.

[abhisays]

Give me some time, I will try to solve these puzzles.

By the way, good job.

:bravo::bravo:

[Ashutosh]

The island puzzle is insane. I'm sure that the answer will drive you nuts.

[abhisays]

The island puzzle is insane. I'm sure that the answer will drive you nuts.

That's why I renamed the thread to "Puzzles to puzzle you" :gm::gm::gm:

[Ashutosh]

A highly addictive chess puzzle:

What are the five moves in a chess game that starts with the white king's pawn moving 2 squares ahead (e2-e4) and ends with a black knight capturing a white rook leading to a check-mate?

Kasparov and Karpov couldn't solve it :omg:.

There an interesting story about this here (http://www.chessbase.com/puzzle/puzz05d.htm).

I won't post more until someone cracks one of these. Remember: The fun is in trying and not reading the answers.

[abhisays]

Imagine you are an ant sitting on the face of a Rubik's cube (http://en.wikipedia.org/wiki/Rubik%27s_Cube) made of cheese. You have been assigned the following task: Eat the whole cube by starting with any subcube on the face. Once you're done with a given subcube, you can move to another subcube which shares a face with the one you just finished. The catch is this: The subcube at the center of the Rubik's cube must be the last subcube eaten.

So the puzzle is: Can you do it?


I think the answer is NO.

Let's divide the rubik Cube (27 pieces)

eight 3 faced pieces which are corner Pieces, I will call them '3F'
twelve 2 faced pieces ('2F')
Six 1 face pieces('1F')
And there is one center piece (not visible in rubik Cube, let's call it 'OF')
It is clear that each of the Odd faced piece(3F,1F) is always adjacent to an even faced piece(2F,0F).

So if the ant starts from 3F and after completing 26 pieces, I think it should be at an even faced piece which can't be adjacent to 0F because 0F is also an even faced piece.

That's why the answer should be NO, it is not possible for eat the centre subcube.

[Ashutosh]

Awesome solution! :iagree:

You explained the case when the ant starts at 3F. The other cases are also easy to eliminate as follows:

Once again note that there are 14 odd faced squares but only 12 even faced (discounting the center). Suppose you start at an odd face. Then the 25th square visited by you must be odd and you are left with 1 odd and the central square. The next square that you visit must be the center and you lose this way. If, on the other hand, you start with an even face, then the 24th square visited by you is odd and you're left with 2 odd squares and the central square. The next square that you can eat is again the central square and you lose pretty bad in this case.

A small remark: If you visualized the rubik's cube as being made of black and white squares like a checker board then your odd/even terminology corresponds to black/white squares.

[jitendragarg]

For the eye colour problem, second situation will occur, if the foreigner mentioned number of blue coloured eyed people.

Else, even if the blue eyed people can see 999 other people, they won't be able to logically decide if their eye colour is blue or not. So, every blue eyed person will see atleast 99 other blue eyed person, hence, the statement of foreigner will be valid even if the 100th person is not blue eyed. So, 100th person will never know if he is blue eyed or not. So, he should not commit suicide, unless other members of the group tell him about his eye colour.

I might be wrong here, but I guess, my logic stands valid. If not, I will wait for your solution.

[jitendragarg]

I have added tags for this thread.

Also, puzzles are really good, and not the same old crap, I am used to solve during interviews.

:cheers:

[Ashutosh]

Here's a hint for blue eyed puzzle: Consider the same problem with instead of 900/100 brown/blue eyed people, 999/1 brown/blue eyed people. Too easy? Now try 998/2. What about 997/4? Can you see something now?

[jitendragarg]

Already thought of it that way. For 999/1 its fairly simple.
Now, for 998/2, there are 2 persons, A and B. Person A will see colour of B's eyes, and he will think that foreigner was talking about B, and vice-versa, meaning no suicides. Similar logic can be extended for 900/100 eye colour ratio. I know my logic may be faulty, and I am missing something very basic here, but till now, I am still happy with my solution.

[Ashutosh]

For the case 998/2, here's what happens:

Say A and B have blue eyes. Before the vistor's statement, this is what A might have been thinking:

"This dude B has very pretty blue eyes. I wonder if I have such pretty eyes."

B's thoughts are completely symmetric.

Now what can change after visitor's statement? Here are A's thought just after the statement was made:

"Do I have blue eyes? Let's see. Say I don't. Then, I know that B is the only guy with blue eyes. Clearly he now knows that since that idiot visitor made it known that there is someone with blue eyes. So he should kill himself tomorrow. That would be so awesome to watch :party:."

B's thoughts are entirely symmetric. So both A and B wait for the ritualistic suicide. But the fateful moment comes and no one commits suicide. Here's what A's thinking now:

":omg:! Why isn't B dead? Surely because I do have blue eyes and he was waiting thinking that I might die today. Crap! Now I know that I have blue eyes. I'm shooting myself."

B thinks the same and they both immediately commit suicide.

Can you extend the argument to the case 900/100?

[jitendragarg]

Lets do this. Extend your argument, to three person. Say, A and B are blue eyed, and C is not. After the visitor's statement, what will C thinks?

"A and B both have blue eyes, so it will be awesome to watch them die." At the same moment A and b are both thinking other will commit suicide.

Next day, C finds that none of them commited the suicide yet. So, what will he think? Exactly the same as A and B, that he might be also blue eyed. So, by that logic, C should also commit suicide, since no one will tell him that he is not blue eyed.

So, till the time, there is either A or B's suicide, every C person thinks he might be blue eyed and kill himself. Only when A or B will kill himself, then only they will know that the blue eyed person mentioned by visitor is dead now. Till then every brown eyed person will commit suicide.

Also, in that case, as soon as A is dead, B will know that blue eyed person is dead, so, he will think he is not the blue eyed person, unless mentioned by someone else.

Result, B will still live, and since he is still alive every other C will keep commiting suicide. So, the whole group will kill themselves, before B realises that he is the last standing blue eyed person.

So, by that logic, every person will be dead, and not just the blue eyed person.


Now, you can similarly expand my logic to 900/100 people. There will be every time a blue eyed person who thinks he is brown eyed, since all other blue eyed people are dead. So, by the logic you suggested, every person will die, which was not mentioned in any of the situations in the question. So, technically, the solution should be "everyone is dead", and not "all blue eyed people are dead".

[Ashutosh]

A correction. In the case 998/2, both blued eyed men commit suicide 2 days after the visitor's speech (and not 1 day) since the rule says you die a day after you know your eye colour. In the case 900/100, it is exactly 100 days after which all blue eyed people commit suicide all together. To prove this properly we may use induction. For instance in the case 997/3, say blued eyed men are A, B and C. Then A will argue thus:

"Say I didn't have blue eyes. Then A and B will use the 998/2 argument and I should see them die in 2 days from now."

B and C have similar thoughts. But 2 days later no one dies so A, B and C simultaneously deduce that they've blue eyes. Hence on the third day they kill themselves. You can see now how induction works.

The reason why the brown eyed people don't kill themselves is simple. This argument will not work if the visitor hadn't made his statement. The brown eyed men still don't share the "common knowledge" that there are brown eyed people on the island. To see the meaning of common knowledge more clearly, suppose there were only 2 brown eyed people say A and B on the island. Denote by S, the statement "There is at least one brown eyed person on the island". Then while A knows S and B knows S, A doesn't know that B knows S and B diesn't know that A knows S. This is the crux of matter. What the visitor did was that he made S common knowledge.

[Ashutosh]

I forgot to mention that the fact that everyone on the island has either blue or brown eyes isn't known to the natives. Of course, after 99 days all blue eyed people learn this fact but being true men they do not disclose this to the brown eyed men.

[jitendragarg]

I really don't get it. How does it denies my logic? Consider the scenario, that no one knows that there are actually brown eyed or blue eyed people, as you mentioned in your logic. In that case, a person X, no matter what his eye colour is, will still know that there are both brown eyed and blue eyed people, since they can actually see other. And since none of them is blind, person X can easily deduce, that person Y has seen other people's eye colour too. Saying that is not the case, is a remote possibility of having a particular tribe where no one actually ever know any other person of the tribe. And for all possible deductions, normal scenarios are considered, and not some remote exceptions.

So, the answer you gave me, gets invalid at the exact moment when you say, and i quote,

The brown eyed men still don't share the "common knowledge" that there are brown eyed people on the island. To see the meaning of common knowledge more clearly, suppose there were only 2 brown eyed people say A and B on the island. Denote by S, the statement "There is at least one brown eyed person on the island". Then while A knows S and B knows S, A doesn't know that B knows S and B diesn't know that A knows S. This is the crux of matter. What the visitor did was that he made S common knowledge.

Consider the same scenario for three people. Since A, B, C, all knows statement S. And A knows that B and C know each other's eye colour too. So, its clear that A can deduce the simple fact that B and C know the statement S too. Your argument is valid in case of two people. But for any no. of people more than 2, the statement is invalid. So, visitor did nothing exactly. He didn't made anything a common knowledge, as it already was. Only thing he did was to make them talk about the eye colour.

[Ashutosh]

I didn't define common knowledge precisely. Instead of typing it in my words, I'll give you the wikipedia link on common knowledge and a version of the island puzzle:

http://en.m.wikipedia.org/wiki/Common_knowledge_(logic)

[jitendragarg]

Ah! Leave it. That wiki article is missing a very simple logic, but I guess we have discussed it way too far, so lets continue with other puzzles.

:cheers:

[Ashutosh]

Here's another puzzle:

A person X chooses a number between 1 and 16 - so he has 16 choices. You have to guess the number he chose. You can ask him 7 yes/no questions.

Such a question may be:

"Is your number bigger than or equal to 9?"

X is an honest person and won't lie more than once. He may be too honest and could even answer all 7 questions correctly. You don't know beforehand. At the end of these 7 questions, you have to tell X what number he chose.

So the question is: Find a strategy to do this.

If this seemed too easy, show that 6 questions aren't enough to do the job.

[Ashutosh]

Geometric puzzles:

(1) Suppose that every point in plane is coloured red, blue or green. Show that there are two point of same colour which are at a unit distance from each other.

(2) Suppose that every point in plane is coloured red or blue. Show that there is a colour such that there are points of this colour at all possible distances.

(3) Show that you cannot cover the plane by any collection of pairwise non-intersecting circles (i.e., boundaries of circles) of positive radii.

(4) Show that the space can be covered with such circles.

[abhisays]

Here's another puzzle:

A person X chooses a number between 1 and 16 - so he has 16 choices. You have to guess the number he chose. You can ask him 7 yes/no questions.

Such a question may be:

"Is your number bigger than or equal to 9?"

X is an honest person and won't lie more than once. He may be too honest and could even answer all 7 questions correctly. You don't know beforehand. At the end of these 7 questions, you have to tell X what number he chose.

So the question is: Find a strategy to do this.

If this seemed too easy, show that 6 questions aren't enough to do the job.

Let me try this puzzle.

Think of the number in base 2, it has a form abcd where each one of a, b, c, d is either 0 or 1. Now in the first 3 questions I will ask him if a, b, c are 0 whereas in the fourth question I would ask him if he lied in one of the last three questions if he says no then you have 3 more questions to figure out the last digit.

He might have lied in one of these questions but I can repeat my question and see if he lied the difficult case is when he says that he did lie in one of the first three questions then I know that one of the digits a, b, c is wrong so in the next two questions I would ask if a is wrong and if b is wrong so 4 + 2 questions and you know a and b and c correctly you can ask d in the last question. Now this should work because he has already used up his one lie so he must give the right value of d in the last question


:think:

[jitendragarg]

@abhisays

should work, although I am still trying to think how to figure out the fourth digit, if he lies on the fourth question, i.e. when you ask him if he lied in first three questions or not. Say, he didn't lied in any of the three questions, and lies in fourth one, and tells you that he has lied earlier. Now, in that case, what will be your fifth question?
:scratchchin::scratchchin: