Archive for the ‘math tricks’ Category
Both the problems here are based on prisoners and hats….
There are n prisoners in a prison. The prison warden gives them an offer:
He will be asking the prisoners to stand in a queue, ordered based on their heights, tallest in the front of the queue and the shortest at the end such that every prisoner can see the heads of all prisoners in front of him. Now everyone will be blindfolded and a black or a white hat will be placed on every head. Distribution will be random. The warden would then remove the blindfolds and would start asking every prisoner the colour of their hat, in order, starting from the shortest. The prisoner can answer either “black” or “white”. If a prisoner tells the answer correctly, he will be freed, otherwise killed instantly.
The warden gives twenty minutes for the prisoners to discuss the algorithm among themselves. Then the above activity starts.
Out of n prisoners, how many can be saved for sure ? What is the method ?
Here there are only three prisoners. The warden has three white and two black hats, and the prisoners know this fact. The warden announces that he would be placing one cap on each of their heads after blindfolding them. After removing the blindfold, every prisoner will be able to see both the other prisoners.
The warden blindfolds them and places the three white hats on their heads.
Everyone thinks for some time, after which one prisoner answers “white”.
How did the prisoner come to the conclusion that his head had a white hat ?
I come across loads of interesting questions which have been asked in interviews. Just thought of posting them here in my blog…
There is a long table with 100 cups arranged in a line. The cups are numbered from one to hundred. Initially all cups are closed with lids.
This is what you do:
First, you open all cups that are multiples of 1. ( Obviously all hundred cups )
Next, you invert all the cups that are multiples of 2. Inverting a cup refers to opening a cup if it is closed, or, closing a cup if it is open.
Next, you invert all cups that are multiples of 3.
This process is continued for 4, 5. 6, …. 100.
After this is done, how many cups will be open, and what are their numbers ??
There is a standard chess board. ( 8 x 8 ). A horse is placed on a corner square, say, black
The task that is being done is the obvious, move to all squares in the chess board, without landing on a square more than once.
The question is different:
Is it possible to reach the corner that is diagonally opposite to the starting square after moving to all other squares ? If yes, how ? If no, why ?
- All square numbers have odd number of factors. All other numbers have even number of factors.
- To check whether a number is prime, it is sufficient to check its divisibiliy by all prime numbers less than square root of the number.
- A number n is a sum of two squares if and only if all prime factors of n of the form 4m+3 have even exponent in the prime factorization of n.
- if p is a prime number, then for any integer a, ap − a will be evenly divisible by p. This can be expressed in the notation of modular arithmetic as follows.
ap ≡ a (mod p) . This is Fermat’s Little Theorem.
- If an integer n is greater than 2, then the equation an + bn = cn has no solutions in non-zero integers a, b, and c. This is Fermat’s Last Theorem.