Maths Olympiad Prep

Library / /6 of 8

Combinatorics Difficulty 6.0 AIME, harder Find the answer Italy

Problem:

An 88 by 88 chessboard is filled with the letters AA, BB, CC, DD so that two cells sharing a side or a vertex contain different letters, and so that the letters AA and the letters BB have the following property: whenever an AA or a BB has a certain letter XX adjacent horizontally or vertically (XX can be AA, BB, CC or DD), then on the opposite side there is another XX (unless there is the edge of the board). In how many ways is it possible to arrange such letters on the chessboard?

Pick one

Solution

Solution:

The answer is (A). Let us number the rows from 11 to 88 and the columns from 11 to 88; consider the central 2×22 \times 2 square, the one formed by columns 44 and 55 intersected with rows 44 and 55. We examine two cases separately:

a. In the square we place an AA and a BB in cells that meet at a vertex, and a CC and a DD in the two remaining cells; we can do this in 88 different ways. Once the square has been filled in one of these ways, there is one and only one way to complete the entire chessboard.

b. The AA and the BB placed in the central square are horizontally or vertically adjacent (we can fill the square in 4!84! - 8 ways so that this happens). Suppose that AA is located in row 44, column 44 and BB in row 44, column 55 (the other cases are perfectly analogous). Row 44 must be filled with AA and BB alternating; row 55 must in turn contain CC and DD alternating (starting with CC or with DD depending on how we filled the central square). The odd rows must all be identical to row 55. The even rows will contain AA and BB alternating: in row 44 the starting letter is fixed (in our case it is AA) but for all the other even rows (22, 66 and 88) we can choose (independently) whether they start with AA or with BB. Altogether we have counted (4!8)23(4! - 8) 2^3 configurations.

In total the admissible configurations are therefore 136136.

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 translated into English from it; metadata (topic, difficulty) added by this project.