Puzzles or short exercises illustrating mathematical problem solving to freshman students At high school, the solution method to almost all mathematical exercises is to apply some technique or algorithm you have learned before. At the university, the situation is fundamentally different. Many exercises have the flavor of little research problems, where it is not obvious at all how to start. This new experience can be frustrating even to the most talented students.
I'm looking for puzzles or small exercises to illustrate "mathematical problem solving" to freshman students. Ideally, such a problem statement meets the following requirements:


*

*Easy to understand. The involved notions should be familiar from high school mathematics or daily live, and not be built upon a framework of abstract definitions. Suitable problems often come from combinatorics, elementary geometry or elementary number theory. Some abstractness is ok, since this is another point freshman students have to get used to.

*Exciting or fascinating in some way. No dry theory questions.

*The question should be suitable to get your hands on and "do reasearch" with it (if necessary, by giving hints). For example by looking at special cases, investigating the consequences of modified requirements, etc.

*The solution should not be obvious and require some clever idea. Furthermore, it should be possible to give a rigorous solution/proof, without involving long calculations, and like the question, only relying on methods which are well-known to a freshman student.
I will some give some examples of good problems (in my opinion) as answers below.
Please give only one problem statement per answer.
 A: "Sam Loyd's" 14-15 Puzzle

Can the tiles in the below arrangement be put in order by just sliding them around?


(Answer: No.  Every legal move retains the parity of the sum of the number of inversions and the row number that the blank appears on.  It is easy to see that the given position has odd parity, and the home position has even parity.)
The solution might be a tad advanced, but with some guidance I think it is attainable.  Since it was a (short-lived) craze in the 1880s, it must be fascinating and exciting!
A: This is a classical one (On wikipedia):

Given an $8 \times 8$ grid where two diagonally opposite corner squares are removed. Is it possible to cover the 62 remaining squares by rectangles of size $2\times 1$?

(Answer: Imagine the squares of the grid are colored in black and white like a chessboard...)
Here, one can look at smaller boards first, and modify the pattern of the removed squares (don't remove any square; remove a single square; remove two adjacent corner squares, etc.).
A: One of my favourites is the game of 15, in which people take turns picking numbers from 1 to 9 (without repeating) and try to get three of them that add up to 15. Try and devise a winning strategy for it.
Hint: It teaches people about isomorphism.
A: I've found the following in the book The Man Who Loved Only Numbers about Paul Erdős. It is a little gem in my opinion:

Let $n$ be a positive integer. True or false: Each subset of $\{1,\ldots,2n\}$ of size $n + 1$ contains a pair of coprime numbers.

(Answer: true, since there must be a pair of adjacent numbers.)
Ways of experimenting with this problem include looking at special cases for small $n$, and looking at subsets of different size (especially $n$ instead of $n+1$).
A: A man starts at the bottom of a mountain at 8 am and reaches the top at noon. He spends the night at the peak and starts down the mountain at 8 am the next day, reaching the bottom at noon. He follows the only path that exists on both days. Show that there must be at least one point on the path that he occupied at the same time each day. 
Spoiler: A hint is given below.
The hint is to think of his 2 journeys as happening simultaneously. 
A: How many squares are on a chess board? 
You can ask it about a Go board too but not many kids have seen that.
Question is about counting squares of ALL sizes.
Answer for an $n*n$ board is $1^2+2^2+\cdots+n^2$.
Illustration for boards of different sizes.
A somewhat similar problem for triangles.
A: 
There are 2 points on earth that are diametrically opposite to each other, and have the same temperature and pressure.

You can ask them to show that on the equator, there are 2 points diametrically opposite to each other, which have the same temperature.
Uses Intermediate Value Theorem, and they might have seen the 2-D version in high school already.
A: Domino tiling

How many ways are there to tile a $2\times n$ rectangle by dominoes of size $1\times 2$?

Visualization of the tilings for $n\leq 6$:

The problem can be investigated for small $n$ and has a surprising answer (Fibonacci numbers). The formal proof relies on induction and is a nice way to apply and watch this technique in a quite visible way.
A: 
5 points are placed on a sphere. Show that there is a (closed) hemisphere which contains at least 4 points.

You can give a hint of "If we blindly take any cut of the sphere, by the pigeonhole principle,  one of these hemispheres must contain at least 3 points."

 Answer: Take any 2 points, and consider their great circle, which forms 2 hemispheres. By the Pigeonhole principle, out of the remaining 3 points, at least one of them must have 2 points on it. Hence we are done.

A: 
There is a thin horizontal railing, say 10 ft long, running North/South. At time $t=0$ one hundred ants fall onto the railing, at random locations and each initially facing randomly either North or South. Upon making contact with the railing all the ants begin a forward march at the speed of 10 ft per minute. The railing is thin so that whenever two ants knock antlers, they both immediately turn on their six heels and start heading in the opposite direction. Whenever an ant reaches the end of the railing, it gently floats to the ground and stays there.
How long will it take for the railing to be clear of ants in the worst case? Assume that the ants are pointlike and need zero time to turn.

No hint here. A spoiler only:

 What would change, globally speaking, if the ants would be able to walk thru each other?

If no light bulb flashes quickly, one may be to try with two, three, four ants... Often a good approach to try a simpler case first.
A: The locker puzzle:

In a hallway there are 100 closed lockers. 
  Now 100 persons pass the hallway.
  The first one changes the state (open or closed) of every locker.
  The second one changes the state of every second locker, the third person of every third locker and so on.
Which lockers will be open in the end?

(Answer: The lockers whose position is a perfect square.)
One can investigate this problem by doing it explicitely for numbers like 10 or 20. If some results are found, the correct answer can be conjectured.
The last step is then to rigorously prove the conjecture.
