Maths Olympiad Prep

Library / /88 of 94

Combinatorics Difficulty 5.5 AIME, harder Prove it United States

Problem:

Boris was given a Connect Four game set for his birthday, but his color-blindness makes it hard to play the game. Still, he enjoys the shapes he can make by dropping checkers into the set. If the number of shapes possible modulo (horizontal) flips about the vertical axis of symmetry is expressed as 9(1+2+⋯+n)9(1+2+\cdots+n), find nn.

(Note: the board is a vertical grid with seven columns and eight rows. A checker is placed into the grid by dropping it from the top of a column, and it falls until it hits either the bottom of the grid or another checker already in that column. Also, 9(1+2+⋯+n)9(1+2+\cdots+n) is the number of shapes possible, with two shapes that are horizontal flips of each other counted as one. In other words, the shape that consists solely of 3 checkers in the rightmost row and the shape that consists solely of 3 checkers in the leftmost row are to be considered the same shape.)

Solution

Solution:

There are 979^{7} total shapes possible, since each of the 7 columns can contain anywhere from 0 to 8 checkers. The number of shapes symmetric with respect to a horizontal flip is the number of shapes of the leftmost four columns, since the configuration of these four columns uniquely determines the configuration of the remaining columns if it is known the shape is symmetric: 949^{4}. Now we know there are 97−949^{7}-9^{4} non-symmetric shapes, so there are 97−942\frac{9^{7}-9^{4}}{2} non-symmetric shapes modulo flips. Thus the total number of shapes modulo flips is 94+97−942=94(1+93−12)=94(93+12)=38(36−1)2=9(1+2+⋯+36)9^{4}+\frac{9^{7}-9^{4}}{2}=9^{4}\left(1+\frac{9^{3}-1}{2}\right)=9^{4}\left(\frac{9^{3}+1}{2}\right)=\frac{3^{8}\left(3^{6}-1\right)}{2}=9\left(1+2+\cdots+3^{6}\right), so n=36=729n=3^{6}=729.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.