Consider a board with $n$ rows and $4$ columns. In the first line are written $4$ zeros (one in each house). Next, each line is then obtained from the previous line by performing the following operation: one of the houses, (that you can choose), is maintained as in the previous line; the other three are changed: * if in the previous line there was a $0$, then in the down square $1$ is placed; * if in the previous line there was a $1$, then in the down square $2$ is placed; * if in the previous line there was a $2$, then in the down square $0$ is placed; Build the largest possible board with all its distinct lines and demonstrate that it is impossible to build a larger board.
Problem
Source: Cono Sur 1997, Problem 4
Tags: cono sur, combinatorics
kootrapali
12.05.2018 03:41
I don't quite understand.
NiltonCesar
12.05.2018 04:38
kootrapali wrote: I don't quite understand. Hey man... I change some of the question.... There is some weird part yet? Let me take an example to ilustrate this: $0 0 0 0$ $0 1 1 1$ (I choose the first columm to keep the same) $1 1 2 2$ (I choose the second columm to keep the same) $2 2 2 0$ (I choose the third columm to keep the same)
kootrapali
12.05.2018 05:46
But couldn’t the board go on indefinitely?
NiltonCesar
26.12.2018 01:12
kootrapali wrote: But couldn’t the board go on indefinitely? No
chaotic_iak
27.12.2018 10:37
Rephrasing: a $n \times 4$ board has the property that the first row is all 0, and from a row to the one beneath it, one column has the same number, while in the other three columns the numbers in them increase by 1 modulo 3. How many rows at most can the board have? The sum of all cells in a row is constant modulo 3. At the beginning this is 0, so the sum of all cells is always 0 modulo 3. After we choose the first 3 columns of a row, the fourth is fixed, so there are $3^3 = 27$ different rows possible. This is achievable: 0000 0111 0222 1200 1011 1122 2100 2211 2022 0120 0201 0012 1020 1101 1212 2220 2001 2112 0210 0021 0102 1110 1221 1002 2010 2121 2202