Game of Fifteen, 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 (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. The parity argument is accessible even to high school students.
Editors' note accompanying the paper by Johnson & Story (1879) in American Journal of Mathematics is quite interesting:
The "15" puzzle for the last few weeks has been prominently before the American public, and may safely be said to have engaged the attention of nine out of ten persons of both sexes and of all ages and conditions of the community. But this would not have weighed with the editors to induce them to insert articles upon such a subject in the American Journal of Mathematics, but for the fact that the principle of the game has its root in what all mathematicians of the present day are aware constitutes the most subtle and characteristic conception of modern algebra, viz: the law of dichotomy applicable to the separation of the terms of every complete system of permutations into two natural and indefeasible groups, a law of the inner world of thought, which may be said to prefigure the polar relation of left and right-handed screws, or of objects in space and their reflexions in a mirror. Accordingly the editors have thought that they would be doing no disservice to their science, but rather promoting its interests by exhibiting this a priori polar law under a concrete form, through the medium of a game which has taken so strong a hold upon the thought of the country that it may almost be said to have risen to the importance of a national institution. Whoever has made himself master of it may fairly be said to have taken his first lesson in the theory of determinants. It may be mentioned as a parallel case that Sir William Rowan Hamilton invented, and Jacques & Co., the purveyors of toys and conjuring tricks, in London (from whom it may possibly still be procured), sold a game called the "Eikosion" game, for illustrating certain consequences of the method of quaternions. -EDS.