What are Your Favourite Maths Puzzles? We all love a good puzzle
To a certain extent, any piece of mathematics is a puzzle in some sense: whether we are classifying the homological intersection forms of four manifolds or calculating the optimum dimensions of a cylinder, it is an element of investigation and inherently puzzlish intrigue that drives us. Indeed most puzzles (cryptic crosswords aside) are somewhat mathematical (the mathematics of Sudoku for example is hidden in latin squares). Mathematicians and puzzles get on, it seems, rather well.
But what is a good puzzle?
Okay, so in order to make this question worthwhile (and not a ten-page wade-athon through 57 varieties of the men with red and blue hats puzzle), we are going to have to impose some limitations. Not every puzzle-based answer that pops into your head will qualify as a good puzzle—to do so it must

*

*Not be widely known: If you have a terribly interesting puzzle that motivates something in cryptography; well done you, but chances are we've seen it. If you saw that hilarious scene in the film 21, where Kevin Spacey explains the Monty hall paradox badly and want to share, don't do so here. Anyone found posting the liar/truth teller riddle will be immediately disembowelled.

*Be mathematical (as much as possible): It's true that logic is mathematics, but puzzles beginning 'There is a street where everyone has a different coloured house …' are tedious as hell. Note: there is a happy medium between this and trig substitutions.

*Not be too hard: Any level of difficulty is cool, but if coming up with an answer requires more than two sublemmas, you are misreading your audience.

*Actually have an answer: Crank questions will not be appreciated! You can post the answers/hints in Rot-13 underneath as comments as on MO if you fancy.

*Have that indefinable spark that makes a puzzle awesome: Like a situation that seems familiar, requiring unfamiliar thought …

Ideally include where you found the puzzle so we can find more cool stuff like it. For ease of voting, one puzzle per post is best.

Some examples to set the ball rolling

Simplify $\sqrt{2+\sqrt{3}}$

From: problem solving magazine
Hint:

 Try a two term solution



Can one make an equilateral triangle with all vertices at integer coordinates?

From: Durham distance maths challenge 2010
Hint:

 This is equivalent to the rational case



The collection of $n \times n$ Magic squares form a vector space over $\mathbb{R}$ prove this, and by way of a linear transformation, derive the dimension of this vector space.

From: Me, I made this up (you can tell, can't you!)
Hint:

 Apply the rank nullity theorem

 A: From Mathematical Puzzles by Peter Winkler:
Divide an hexagon in equilateral triangles, like in the figure. Now fill all the hexagon with the three kinds of diamonds made from two triangles, also shown in the figure. Prove that the number of each kind of diamond is the same.

A: The odd town puzzle.
You have a town with $m$ clubs formed by $n$ citizens of the town.
The clubs are so formed that


*

*Each club has an odd number of members.

*Any two clubs have an even number of common members. (Could be zero too).


Show that $m \le n$.
A: unknown source:
Could the plane be colored with two different colors (say, red and blue) so that there is no equilateral triangle whose vertices are all of the same color?
A: You are on the surface of a cube, starting at the midpoint of one of the edges.  Which point(s) on the cube is furthest away from you if you are constrained to travel on the surface of the cube? 
A: Is it possible to divide a circle into a finite number of congruent parts some of which don't touch the center?
A: Assuming you have unlimited time and cash, is there a strategy that's guaranteed to win at roulette?
A: The Blue-Eyed Islander problem is one of my favorites.  You can read about it here on Terry Tao's website, along with some discussion.  I'll copy the problem here as well.

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?

A: Here are three of my favorite variations on the hats and prisoners puzzle that I've collected over time:


*

*Fifteen prisoners sit in a line, and hats are placed on their heads. Each hat can be one of two colors: white or black. They can see the colors of the people in front of them but not behind them, and they can’t see their own hat colors. Starting from the back of the line (with the person who can see every hat except his own), each prisoner must try to guess the color of his own hat. If he guesses correctly, he escapes. Otherwise, he is fed to cannibals (because that’s the canonical punishment for failing at hat problems). Each prisoner can hear the guess of each person behind him. By listening for painful screaming and the cheering of cannibals, he can also deduce if each of those guesses was accurate. Of course, this takes place in some magical mathematical universe where people don’t cheat. Assuming that they do not want to be eaten, find the optimal guessing strategy for the prisoners. (The cannibals should eat no more than one prisoner.)

*In the year 3141, Earth’s population has exploded. A countably infinite number of prisoners sit in a line (there exists a back of the line, but the other end extends forever). As in the previous problem, white and black hats are placed on their heads. Due to modern technology, each person can see the hat colors of all infinitely many people in front of them. However, they cannot hear what the people behind them say, and they do not know if those people survive. Assuming that they do not want to be eaten, find the optimal guessing strategy for the prisoners. Assume that there are enough cannibals to eat everyone who fails. (The cannibals should eat no more than finitely many prisoners. Assume the Axiom of Choice.)

*There are seven prisoners, and colored hats will be placed on their heads. The hats have seven possible colors (red, orange, yellow, green, blue, indigo, violet), and may be placed in any arrangement: all the same color, all different colors, or some other arrangement. Each person can see everyone else’s hat color but cannot see his own hat color. They may not communicate after getting their hats, and as in the previous problems, they remain in a magical universe where no one cheats. They must guess their hat colors all at the same time. If at least one person guesses correctly, they are all released. If no one guesses correctly, however, the entire group is fed to cannibals. Assuming that they don’t want to be eaten, find the optimal guessing strategy for the prisoners. (By this point, the cannibals have probably eaten far too much. It would be cruel to force them to eat any more, so spare the cannibals and find a way to guarantee that the seven prisoners survive.)
A: Fork in the road 2
You're once again at a fork in the road, and again, one path leads to safety, the other to doom.
There are three natives at the fork.  One is from a village of truth-tellers, one from a village of liars, one from a village of random answerers.  Of course you don't know which is which.
Moreover, the natives answer "pish" and "posh" for yes and no, but you don't know which means "yes" and which means "no."
You're allowed to ask only two yes-or-no questions, each question being directed at one native.
What do you ask?
A: Relatively simple, but still fun...
Unknown source, other than my friend telling me yesterday
There is a room with 50 doors in it, each door leading to a cell that is completely sound-proof and light-proof, and each cell can hold a maximum of 1 person.  There are 50 prisoners.  There also exists a light in the middle of the main room, so that when a prisoner is pulled out of their cell, they could see the light.  There is also a light switch inside the main room which controls the light.  The 50 prisoners are the only people allowed to touch the light switch that controls the light (even the prison guard cannot touch it)
Before any prisoner is placed in the cells, the prison guard tells them that he will pull out, at random, any one of them at any time, and then put them back in their cell after they get a chance to turn the light on or off or do nothing at all to it. (Only one prisoner can be out of their cell at any given time)  He also guarantees them that he will pull at least one prisoner out at least once a day.
The goal is, when any one prisoner knows when all 50 prisoners have been pulled out of their cells at least one time, and he tells the prison guard this fact correctly, all prisoners will be let free.
The prisoners are allowed one short meeting before they all get placed in their cells.
They also have a (reasonably) infinite amount of time to let the prison guard know when all prisoners have been let out of their cells at least one time.  (say 5 years or something to that effect)
There is only one guess allowed ever, so it better be the right answer, or else they will all be fed to the cannibals.
What method did they come up with to know exactly when all 50 prisoners have been out of their cells at least one time?
A: Quite simply, a monkey's mother is twice as old as the monkey will be when the monkey's father is twice as old as the monkey will be when the monkey's mother is less by the difference in ages between the monkey's mother and the monkey's father than three times as old as the monkey will be when the monkey's father is one year less than twelve times as old as the monkey is when the monkey's mother is eight times the age of the monkey, notwithstanding the fact that when the monkey is as old as the monkey's mother will be when the difference in ages between the monkey and the monkey's father is less than the age of the monkey's mother by twice the difference in ages between the monkey's mother and the monkey's father, the monkey's mother will be five times as old as the monkey will be when the monkey's father is one year more than ten times as old as the monkey is when the monkey is less by four years than one seventh of the combined ages of the monkey's mother and the monkey's father.  
If in a number of years equal to the number of times a monkey's mother is as old as the monkey, the monkey's father will be as many times as old as the monkey as the monkey is now, and assuming no a priori knowledge of the monkeys' longevity, find their respective ages. :-D
A: From New Scientist some years ago:  20 teams play a round robin tournament, each gets 1 point for a win, 0 for a loss, and there are no ties.  Each team's score is a square number.  How many upsets occurred? An upset is defined as team A defeating team B where B scored more total points than A.
A: If you have 32 2x1 dominoes then you can cover an 8x8 board easily enough; if you throw away a domino and cut a 1x1 square from each end of a diagonal of the board, can you cover the remaining shape with the remaining dominoes?
I heard this decades ago at university.
A: A regular tetrahedron and a regular square pyramid both have unit length. If a triangular face of the tetrahedron is glued to a triangular face of the square pyramid, the resulting shape has how many edges? 
A: Prove that any 2-coloring of a $K_6$ has two monochromatic $K_3$'s.
A: A probability problem I love.
Take a shuffled deck of cards. Deal off the cards one by one until you reach any Ace. Turn over the next card, and note what it is.
The question: which card has a higher probability of being turned over, the Ace of Spades or the Two of Hearts?
A: Most of us know that, being deterministic, computers cannot generate true random numbers.
However, let's say you have a box which generates truly random binary numbers, but is biased:  it's more likely to generate either a 1 or a 0, but you don't know the exact probabilities, or even which is more likely (both probabilities are > 0 and sum to 1, obviously)
Can you use this box to create an unbiased random generator of binary numbers?
A: A personal favorite (albeit not ideally-worded): Jamie has a windowbox where he plants a row of iris flowers.  He plants in just two colors - blue and yellow - but never plants two yellow irises next to each other (the result is just too garish).  Assuming that he wants to keep the same number of flowers in his box every day, how many flowers will he need if he wants a different arrangement of blue and yellow every day for a year?
A: Not a mathematical puzzle in the classical sense, but it is an interesting variation on the men with hats problem. It has a much "quicker" solution which to some degree is a bit surprising. If you are willing to indulge me, I will also add a rich background story.
After Hilbert passed away in 1943 his grand hotel stood empty for some years until it was bought by a mad version of Stalin and was turned into a crazy prison for the infinitely many enemies of the state.
Several days later the prison is full, and Stalin being less-mathematically inclined than Hilbert decides that instead of moving all the prisoners he will execute them. Since mathematicians can be useful to the Soviet Union he decides to play a game.
He announces that in the morning of the next day every prison will be given a hat either black or white (but not both), and the prisoners will be standing in line by their room number, each seeing all those whose room number is larger. Without talking to each other they will have to guess whether or not they wear a white hat or a black hat. If someone guesses the correct color they go free, otherwise they have a meeting with the executioner.
The prisoners all meet at the dining room later that day and devise a strategy in which no infinite number of prisoners will die. What is it?

 The answer is as follows:

 The prisoners consider all the infinite black-white (binary) sequences, they define an equivalence class that two sequences are equivalent if and only if they differ at finitely many coordinates.

 Using the axiom of choice they choose a representative from each equivalence class. The next morning each of the prisoners see a tail of the sequence of the hats and each prisoner knows its index number, therefore they all know a specific sequence which is equivalent to the sequence of hats, and each prisoner can say the color appearing in the coordinate of their room.

 Since the representative is only different in finitely many places than Stalin's choice, almost all prisoners gets to live.

 It is interesting to remark that the prisoners have to use the axiom of  choice, as in models of ZF+AD such choice is impossible.

A: Frk n th rd 1
Y'r n pth n n slnd, cme t  frk n th rd.  Bth pths ld t vllgs f ntvs; th ntr vllg thr lwys tlls th trth r lwys ls (bth villgs cld b trth-tllng r lyng vllgs, r n f ch).  Thr r tw ntvs t th frk - thy cld bth b frm th sm vllg, r frm dffrnt vllgs (s bth cld b trth-tllrs, both lrs, r ne f ch).
n pth lds t sfty, th thr t dm.  Y'r llwd t sk nly n qstn t ch ntv t fgr t whch pth s whch.
Wht d y sk?
A: There is a square table with a pocket at each corner; in each pocket is a drinking glass, which you cannot see. Each glass might be right-side up ("up") or upside-down ("down").
You and an adversary will play the following game. You select exactly two of the pockets, withdraw the two glasses, thus learning their orientations. You then replace the glasses in their pockets, altering their orientations in any way you desire.
If at this point, all four glasses are oriented the same way, you win.
Otherwise, you look away, and the adversary rotates the table.  All the pockets are indistinguishable, so you cannot tell what multiple of $\frac\pi2$ the table has been rotated.
Provide a strategy that is guaranteed to win in bounded time.
A: A time bomb has 25 switches engaged, all in a row and numbered from 1 to 25.  A spy has told you that you could defuse the bomb by flipping every switch, then flipping every multpile of 2, then flipping every multiple of 3, etc through multiples of 25 (then you are done, there are no numbers greater than equal to 26).  But the bomb will go off shortly.  Which switches do you flip to get the correct combination as quickly as possible?
A: For solving any mathematics series below algorithm can be used. Even for some cases it will not satisfy your expected answer, but it will be correct in some other way.
Steps are as below:
1) Get difference between the numbers as shown below:
2) Keep making difference until it seems same(difference get 0).
3) Put the same last number which are coming same in that sequence and by adding that difference complete the series by coming up.

Examples are as below:

1       2       3       4       5       6       **7**

   1        1       1       1       1       **1**   


1       4       9       16      25      **36**      
     3      5       7       9       **11**          
        2       2       2       **2**               



1       8       27      64      125     **216**     
    7       19      37      61      **91**          
        12      18      24      **30**              
            6       6       **6**                   
                0       **0**                       



The same above algorithm is implemented in below js code.

//the input

var arr=[1,4,9,16];

var pa6inoArrayMelvo = function(arrr){
var nxtArr=[];
    for(i=0;i1){

          tempArr=pa6inoArrayMelvo(ar);       
          keepAlltheArray(tempArr);
        }else{
            generateArray(keepArray.length-1);
            console.log("ans is:"+keepArray[0]);
        }


}

var generateArray=function(idx){
    if(keepArray[idx+1]){
        var a=keepArray[idx+1];
        var b=keepArray[idx];
        var ans=a[a.length-1]+b[a.length-1];
        keepArray[idx].push(ans);
    }else{
        var ans=keepArray[idx][keepArray[idx].length-1];
        keepArray[idx].push(ans);
    }
    if(idx>0){
        generateArray(idx-1);
    }
}

keepAlltheArray(arr);


