Competition problem — Combinatorics

Library / /279 of 520

Combinatorics Difficulty 5.6 AIME, harder Prove it

The game of Taquin consists of 15 squares of area 1 placed on a square of area 16 as shown in Figure 10. Can we start from the configuration where every square is in its place and reach the configuration where 15 and 14 have been swapped while leaving the others in place? It is specified that a move consists of moving the "hole" into an adjacent horizontal or vertical space.

## - Corrected exercises -

Solution

The initial and final configurations have different parities. Each move is a transposition, of signature -1, so we need an odd number of moves.

We color the squares of the large square like the squares of a chessboard. At each move, the hole changes color. At the beginning and at the end, it has the same color. Thus, the number of moves is even. Contradiction.

## 5 Test

## - Statements (duration: $3 h 30)$ -

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.