Competition problem — Combinatorics

Library / /30 of 63

Combinatorics Difficulty 6.8 National olympiad Prove it Japan

In a $7 \times 7$ chessboard, a coin is placed in the square in the first row from the top, the fourth column from the left. We call square $Y$ a lower left square of square $X$ if $Y$ is $k$ squares to the left and $k$ squares below $X$ for some positive integer $k$ . Similarly, we call square $Y$ a lower right square of square $X$ if $Y$ is $k$ squares to the right and $k$ squares below $X$ for some positive integer $k$ . For a square $X$ not on the bottom line, one can perform one of the following four operations when a coin is placed on $X$ :

a. Remove a coin from $X$ and place a coin in the square one below $X$ .

b. Remove a coin from $X$ and place coins in each of the lower left squares of $X$ .

c. Remove a coin from $X$ and place coins in each of the lower right squares of $X$ .

d. Remove a coin from $X$ and place coins in the square one square to the left and one square below $X$ , and the square one square to the right and one square below $X$ . If there is only one such square, place a coin in that square only.

If there is already a coin in the place where one intends to place a coin, one will not place the coin there.
Find the maximum possible number of coins that can be placed on the square when the operation is performed an arbitrary number of times.

(a)

(b)

(c)

(d)

Solutions — 2

Solution 1

$19$

If one writes the number in each square as shown in the figure below, the sum of the numbers written in the squares where the coins are placed cannot be increased by the operations.

The number written in the square where the coin was initially placed is $64$ and there are three squares with $1$ written in them, eight squares with $2$ and six squares with $4$ . Since the number written in each of the other squares is at least $8$ , $64 < 1 \cdot 3 + 2 \cdot 8 + 4 \cdot 6 + 8 \cdot 3$ shows that the number of coins placed in the squares is always less than or equal to $3 + 8 + 6 + 3 - 1 = 19$ .

On the other hand, one can place $19$ coins in the squares by performing the operations as follows. In the following operation $(x)$ on the square in $i$ th row from the top and $j$ th column from the left is denoted by " $x$ on $(i, j)$ ".

Do $d$ on $(1, 4)$ , $b$ on $(2, 5)$ , $a$ on $(5, 2)$ , $d$ on $(6, 2)$ , $d$ on $(4, 3)$ , $a$ on $(5, 2)$ , $d$ on $(5, 4)$ , $d$ on $(6, 3)$ , $d$ on $(6, 5)$ , $d$ on $(3, 4)$ , $d$ on $(4, 3)$ , $a$ on $(4, 5)$ , $d$ on $(5, 5)$ , $d$ on $(6, 6)$ , $d$ on $(5, 4)$ , $c$ on $(2, 3)$ , $a$ on $(5, 6)$ , $d$ on $(4, 5)$ , $d$ on $(3, 4)$ in that order.

From the above, the answer is $19$ .

Solution 2

The proof that the number of coins placed in the squares is at most $19$ is the same as above. One can also place $19$ coins in the squares by performing the operations as follows.

Do $d$ on $(1, 4)$ , $d$ on $(2, 3)$ , $d$ on $(3, 2)$ , $d$ on $(4, 3)$ , $a$ on $(5, 2)$ , $d$ on $(6, 2)$ , $d$ on $(5, 4)$ , $d$ on $(6, 3)$ , $d$ on $(6, 5)$ , $d$ on $(3, 4)$ , $a$ on $(4, 3)$ , $d$ on $(5, 3)$ , $d$ on $(4, 5)$ , $d$ on $(5, 4)$ , $a$ on $(5, 6)$ , $d$ on $(6, 6)$ , $d$ on $(2, 5)$ , $d$ on $(3, 6)$ , $d$ on $(4, 5)$ , $a$ on $(5, 6)$ , $d$ on $(3, 4)$ , $b$ on $(4, 3)$ , $c$ on $(4, 5)$ in that order.

From the above, the answer is $19$ .

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.