Medium | Strategy |

100 prisoners are lined up and assigned a random hat These hats are available in 10 different unique and distinguishable colors. Each prisoner can see the hats in front of him but not behind. Starting with the prisoner in the back of the line and moving forward, they must each, in turn, say only one word which must be the color like "red" or "blue" or "green" etc. If the word matches their hat color they are released, if not, they are killed on the spot. They can hear each others answers, no matter how far they are on the line. What strategy should be used to help release maximum number of prisoners?

Hint

Try prisoner's Hat puzzle first

Solution

Call the first person in back of row the 100th prisoner. The 10 colours will be given codes from 0 to 9. The 100th prisoner will sum the numbers associated with the 99 colours he sees and will say the colour corresponding to it modulo 10. This is enough for 99th person. All he needs to do now is connect the dots, sum the number of hats he can see, calculate modulo 10, and compare it with what 100th prisoner said. This way all 99 prisoners will be saved, and 100th prisoner dies with probability 9/10.

Medium | Strategy |

N people team up and decide on a strategy for playing this game. Then they walk into a room. On entry to the room, each person is given a hat on which one of the first N natural numbers is written. There may be duplicate hat numbers. For example, for N=3, the 3 team members may get hats labeled 2, 0, 2. Each person can see the numbers written on the others' hats, but does not know the number written on his own hat. Every person then simultaneously guesses the number of his own hat. What strategy can the team follow to make sure that at least one person on the team guesses his hat number correctly?

Hint

Modulo?

Solution

Let the persons be numbered 0 to N-1. The i-th person should announce 1 + (i-s)mod N, where s is the sum of numbers he sees. With this strategy, if the sum of all N numbers equals 1 + (m mod N), then the m-th gnome is guaranteed to announce the number of his own hat!

Source: lieno

Enable Like and Comment Medium | General |

I guessed 3 natural numbers - x,y,z. You can ask me 2 sums of these numbers with any integer coefficients - (a,b,c). That is, you give me a, b and c and I tell you the result of the expression a*x+b*y+c*z. Seeing the answer, you then give me the 2nd triplet of (a,b,c) & I will tell a*x+b*y+c*z. Give me the algorithm to find x,y and z.

Hint

If digits are small, we can solve any number of variables by asking a=1, b=10^100, c=10^200 etc just by reading these numbers between the zeros of result.

Solution

Since they are natural numbers, if you knew the maximum number of digits any of them can have, say d, you could set a=1, b=10^d, c=10^2d, and you would be able to read the d-digit numbers directly. So, you use the first calculation to find the maximum number of digits, (a,b,c)=(1,1,1). let d = digits of this result (x+y+z)

Then, set (a,b,c) = (1, 10^d, 10^2d) Let the sum be S.

Then x = (first d digits of S), y = [d+1] to 2d-digits of S, z = [2d+1 to 3d] digits of S

Thus, we note that its posssible to solve for n natural numbers x_1,x_2,...x_n with just 2 questions.

Then, set (a,b,c) = (1, 10^d, 10^2d) Let the sum be S.

Then x = (first d digits of S), y = [d+1] to 2d-digits of S, z = [2d+1 to 3d] digits of S

Thus, we note that its posssible to solve for n natural numbers x_1,x_2,...x_n with just 2 questions.

Source: Quantnet Forums

Enable Like and Comment Medium | Discrete Maths |

An 8x8 chessboard can be entirely covered by 32 dominoes of size 2x1. Suppose we cut off two opposite corners of chess (i.e. two white blocks or two black blocks). Prove that now it is impossible to cover the remaining chessboard with 31 dominoes.

Hint

The two diagonally opposite corners are of the same color.

Solution

The two diagonally opposite corners are of the same color. A domino covers adjacent faces & hence a domino always covers 1 black and 1 white square. The 31 dominoes will cover 31 blacks and 31 whites. The chess has 30 & 32 square instead. Hence this can't be done.

Source: Martin Gardner

Enable Like and Comment Medium | Discrete Maths |

13 Apples, 15 Bananas and 17 Cherries are put in the magic hat. When ever a collision of two different fruits occurs, they both get converted into the third type. For example 1 Apple and 1 Banana can collide to form 2 cherries. No other collision is holy. Can a sequence of such magical collisions lead all 45 fruits to give just one type?

Hint

This can't be done. Try to create a function of A,B,C which remains constant during a collision to get contradiction.

Solution

Create the invariant function f(A,B,C) = (0A+1B+2C)mod3, this function remains constant during a collision. But f(13,15,17) = 1 is not same as any of final states f(45,0,0)=f(0,45,0)=f(0,0,45)=0. Hence this can not be done.

A refreshment to this old trick was given by Aritro Pathak:

call the no of times apples are increased by 2 as A, bananas increased by 2 as B, and cherries increased by 2 as C. if we need 45 apples,total increments - decrements of apple = 32

but increments of apple = 2*A;

when ever 2 banana's are created, 1 Apple is lost, similarly for 2 cherries

decrements = B+C

thus we have 2A-B-C=32, -2B+C+A=15, -2C+B+A=17. Subtract the last two to get 2=3*(B-C) which is impossible. similar cases for when you want 45 of either cherries or bananas.

A refreshment to this old trick was given by Aritro Pathak:

call the no of times apples are increased by 2 as A, bananas increased by 2 as B, and cherries increased by 2 as C. if we need 45 apples,total increments - decrements of apple = 32

but increments of apple = 2*A;

when ever 2 banana's are created, 1 Apple is lost, similarly for 2 cherries

decrements = B+C

thus we have 2A-B-C=32, -2B+C+A=15, -2C+B+A=17. Subtract the last two to get 2=3*(B-C) which is impossible. similar cases for when you want 45 of either cherries or bananas.

Latest solved Puzzles

Color Switches Weird Sequences Intersecting Pillars Consecutive sums Scaling a Square Difficulty Level

© BRAINSTELLAR |