Problem of the Week

Let x = x1x2...xn be a word. For some pair of positive integers 1 ≤ a ≤ b ≤ n, define a substring of x to be a word of the form xaxa+1...xb−1xb. Show that there are at most n distinct palindromic substrings of x.

On each turn, the man who does not speak gains information about their own number. Let A be the first person who speaks, and B be the second.

— B knows his number is not 1.

— A knows his number is not 1 or 2.

— B knows his number is not 2 or 3.

— A knows his number is not 3 or 4.

— B knows his number is not 4 or 5.

— A knows his number is not 5 or 6.

— B knows his number is not 6 or 7.

— Then I know my number!

When B says he knows his number, we know that A ≥ 7 and B ≥ 8. If A’s number is 7, B’s must be 8. If A’s number is 8, B’s must be 9. A’s number can not be greater than 8, because then there would still be two possible values for B’s number. Therefore, the answers are (7, 8) and (8, 9).

Two wise men are each wearing a hat labeled with a positive integer. They know the two numbers differ by 1 but do not know which is larger. They take turns speaking:

— I don’t know my number.

— I don’t know my number.

— I don’t know my number.

— I don’t know my number.

— I don’t know my number.

— I don’t know my number.

— I don’t know my number.

— Then I know my number!

What are the two numbers?

The answer is that on the 100th day, all 100 blue-eyed people will leave.

If you consider the case of just one blue-eyed person on the island, you can show that they obviously leave the first night, because they know they're the only one the green-eyed person could be talking about. They look around and see no one else, and know they should leave. So: [Theorem 1] If there is one blue-eyed person, they leave the first night.

If there are two blue-eyed people, they will each look at the other. They will each realize that "if I don't have blue eyes [Hypothesis 1], then that guy is the only blue-eyed person. And if they're the only person, by Theorem 1 they will leave tonight." They each wait and see, and when neither of them leave the first night, each realizes "My Hypothesis 1 was incorrect. I must have blue eyes." And each leaves the second night.

So: [Theorem 2]: If there are two blue-eyed people on the island, they will each leave the 2nd night.

If there are three blue-eyed people, each one will look at the other two and go through a process similar to the one above. Each considers the two possibilities -- "I have blue eyes" or "I don't have blue eyes." They will know that if they don't have blue eyes, there are only two blue-eyed people on the island -- the two they see. So he can wait two nights, and if no one leaves, they know they must have blue eyes -- Theorem 2 says that if they didn't, the other guys would have left. When they see that they didn't, they know their eyes are blue. All three of them are doing this same process, so they all figure it out on day 3 and leave.

This induction can continue all the way up to Theorem 99, which each person on the island in the problem will of course know immediately. Then they'll each wait 99 days, see that the rest of the group hasn't gone anywhere, and on the 100th night, they all leave.

A group of people with assorted eye colors live on an island. They are all perfect logicians--if a conclusion can be logically deduced, they will do it instantly. No one knows the color of their own eyes. Every night, a ferry stops at the island. Any islanders who have figured out the color of their own eyes then leave the island, and the rest stay. Everyone can see everyone else at all times and keeps a count of the number of people they see with each eye color (excluding themselves), but they cannot otherwise communicate. On this island, there are 100 blue-eyed people, 100 brown-eyed people, and 1 green-eyed person. So any given blue-eyed person can see 100 people with brown eyes, 99 people with blue eyes, and 1 person with green eyes, but that does not tell them their own eye color. The only exception to the no communication rule is when the green-eyed person says right before the first night, "I can see someone who has blue eyes." Who leaves the island, and on which night?

Hint: The answer is not that nobody leaves.

The polynomial evaluated at some N can be thought of as an integer in base N. We can only fully discern the original coefficients of p(x) if N is greater than all the coefficients, so then there won't be any carry-overs. To do this, we can have N=p(1)+1. Thus, the only two questions he needs to ask are p(1) and p(p(1)+1). 

Alice's favorite polynomial is p(x), with nonnegative integer coefficients. Bob wants to find this polynomial by asking Alice the value of p(x) for some integer x he chooses. What is the minimal number of questions Bob needs to ask Alice in order to determine p(x)?

First, a small clarification: the prisoners can't communicate in any way. The only things they can do are look at each other's caps and say a color.

Denote white and black as 1 and 0. The first prisoner, our 'sacrifice', should say the sum of all the other prisoners' numbers modulo 2 (i.e. if everybody else is wearing white, they should say 9 x 1 = 9 ≡ 1 (mod 2)). Note that this operation is equivalent to the bitwise XOR operation on the nine "bits" of the prisoners. Now, each of the other nine prisoners immediately knows their number, as they can cross-reference the nine numbers they see with the number the first prisoner speaks to get their own number. Thus, with this optimal strategy, 9 prisoners are guaranteed to live.

Ten prisoners stand in a circle, wearing caps colored white or black. The color of a prisoner's hat is unknown to themself, but everybody else can see their hat. Going around the circle, each prisoner guesses their hat color. They are freed only if they guess correctly. What is the maximum number of prisoners that are freed, and what is the prisoners' strategy for this to happen? Assume that the prisoners can discuss a strategy beforehand.