[Game of Fifteen][1], a.k.a. the 15-Puzzle, was very popular 100+ years ago. The game is still found in stores; for example, you can search Amazon for "15 Puzzle" and get it for about 5 dollars. 

In the paper [Notes on the 15 puzzle][2] (American Journal of Mathematics,
1879, Vol. 2, No. 4, 397-404) W.W. Johnson and W.E. Story showed, via parity argument, that half of the positions in the puzzle [are not solvable][3]. The parity argument is accessible even to high school students. 


  [1]: http://en.wikipedia.org/wiki/15_puzzle
  [2]: https://www.jstor.org/stable/2369492
  [3]: https://en.wikipedia.org/wiki/15_puzzle#Solvability