Competition problem — Combinatorics

Library / /2 of 14

Combinatorics Difficulty 5.8 AIME, harder Prove it Czech Republic

Let us call by an "edge" any segment of length $1$ which is common to two adjacent fields of a given chessboard $8 \times 8$ . Consider all possible cuttings of the chessboard into $32$ pieces $2 \times 1$ and denote by $n(e)$ the total number of such cuttings that involve the given edge $e$ . Determine the last digit of the sum of the numbers $n(e)$ over all the edges $e$ .

(Michal Rolínek)

Solution

The number of edges, which are not involved in a given cutting, is equal to $32$ , because each of these edges must coincide with the common segment of the two fields forming one of the $32$ resulting pieces $2 \times 1$ . Thus each cutting gives a contribution $112 - 32 = 80$ to the sum $S$ of all the numbers $n(e)$ . Consequently, the sum $S$ is a multiple of $80$ and thus its last digit is zero.

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.