Knots, hats and straight lines

Hello again! You are probably reading this blog as you start your new school year – if you’re applying to universities this year, good luck with your applications.
Use these questions to practice your thinking and explanations. Last blog, I gave you two questions to answer. Lets start with the first:
Q1: If x is odd, prove that (x² – 1) is always a multiple of 8.

 
A: Take n to be any integer (positive or negative). 2n is even. So, an odd x=(2n+1)
( x=(2n-1) will also give you the same answer).
Applying (x² – 1),
(2n+1)² – 1 = 4n² + 4n + 1 – 1
= 4n (n + 1)
So, (x² – 1) will always have a factor of 4. And as n and (n+1) are consecutive numbers, one of them will be even. Therefore, we can take this factor of 2 out to the front. So we have a total factor of 4×2 = 8, i.e.
(x² – 1) has a factor of 8, so that (x² – 1) will always be divisible by 8. Here, I’ve reasoned out the answer. You can also apply the Proof by Induction method to solve this question mathematically.

 
Q2: A knotty problem. Here’s a reminder.

Applying the Reidemeister moves (which you can find again from my last blog), we have the following set of operations that can take you from A to B.

Now, for your new interview questions this month

I do hope that no prisons actually do the following, but your questions for this month are taken from age-old logic puzzles that are still used in places where people look for an analytical and problem-solving brain. Anyone who has read about game theory might recognize some elements of it here, but in any case, everyone should be able to have a decent stab at it. Remember, logic will help you.

Q1:
A bored prison guard lines up 3 prisoners in a single line as shown in the diagram, with one behind another. He tells them that he will release those who are able to solve his puzzle. The warden brings in five hats: 3 red and two blue. The three prisoners are blindfolded and each gets one of the 5 hats, picked at random, placed upon his head. Their blindfolds are then removed so that C can see both A and B and both their hats; B can only see A’s hat, and A being at the front of the line can’t see any hats. No prisoner can see the colour of his own hat.

The warden puts his puzzle to the prisoners: “If you can tell me the colour of your own hat I will release you from this prison; answer incorrectly and you will be shot. If you do not know, you can say I don’t know, and you won’t be shot.” First he asks C, then B, then A: “What is the colour of your hat?”
C thinks for a while, then replies: “I don’t know.”
B then thinks for a while, and replies: “I don’t know.”
Finally, A, thinks and replies: “I know the colour of my hat. It is…”
What colour hat is Prisoner A wearing, and how did he know?
Ok, now a tougher question…

Q2:

100 prisoners are lined up in single file and each has either a red or a blue hat placed on his or her head. (Do not assume that there are 50 red and 50 blue hats). No one can see the colour of their own hat, but can see the colour of the hat worn by every person in front of them. Beginning with the last person in the line, each prisoner is asked to name the colour of his or her own hat. If the colour is correctly named, the person lives; if it is incorrect, the person is shot on the spot. Everyone in the line can hear every response as well as hear the gunshot.
Before being lined up, the 100 prisoners are allowed time to discuss their strategy. Once lined up, each person is only allowed to say “Red” or “Blue” when his or her turn arrives, beginning with the last person in line.
What is the best strategy that allows as many people as possible to live?
Hint: there is one plan that will definitely save all but one person, and there’s a 50% chance that the same plan could save everyone.

Good luck! And I’ll have the answers for you next time.