Maths Olympiad Prep

Library / /78 of 92

Combinatorics Difficulty 7.2 National olympiad, round 2 Prove it Iran

A table consisting of 5 columns and 32 rows, which are filled with zero and one numbers, called varied, if no two rows are filled in the same way.
On the exterior of a cylinder, a table with 32 rows and 16 columns is constructed. Is it possible to fill the numbers cells of the table with numbers zero and one, such that any five consecutive columns, table 32×532 \times 5 created by these columns, is a varied one?

Solution

Answer. Yes.

Imagine a 32×532 \times 5 table TT such that the set of its rows is equal to the set of all 5-tuples (b0,b1,,b4)(b_0, b_1, \ldots, b_4) in which  0i4:bi{0,1}\forall\ 0 \le i \le 4 : b_i \in \{0,1\}.

Now consider a 32×1632 \times 16 table RR. Let (ci)(c_i) be the ii-th column and the jj-th column (cj)(c_j) is "consecutive" if and only if ij±1(mod16)i - j \equiv \pm 1 \pmod{16}.

Show the square located in the row rir_i and the column cjc_j with the sign (i,j)(i, j). Also all the tables made of the first, second and third five columns of RR as T1,T2T_1, T_2 and T3T_3 respectively.

Figure 1

Then we will fill the table using the following method: Put a copy of table TT in the squares of table T1T_1 (which means that the values of the corresponding squares in TT and T1T_1 are the same.) And do the same for table T2T_2 and T3T_3. Then the only empty squares of RR are the squares in c16c_{16}.

If we put ωi,16j=15ωi,j(mod2)\omega_{i,16} \equiv \sum_{j=1}^{5} \omega_{i,j} \pmod{2} (1), in which ωi,j\omega_{i,j} means the value of (i,j)(i, j), then there will be an answer for the problem if we stick RR around a cylinder.

Proof. Assuming SS as a set of 5 "consecutive" columns in RR, there can be two conditions:

i) c16Sc_{16} \notin S: Then we knew that SS contains 5 different columns in SS is "nice".

ii) c16Sc_{16} \in S: The other 4 columns in SS (except for c16c_{16},) are copies of 4 different columns in TT, i.e. assume that they are similar to c1,c2,c3c_1, c_2, c_3 and c4c_4 (2). If there exist two rows rir_i and rjr_j in SS (iji \neq j) with equal values, then using (2) we will have:  1k4:ωi,k=ωj,k\forall\ 1 \le k \le 4: \omega_{i,k} = \omega_{j,k} \Rightarrow According to the property that TT is nice, ωi,5ωj,5sisj\omega_{i,5} \neq \omega_{j,5} \Rightarrow s_i \neq s_j, in which sis_i is the sum of ii-th row in TT. But rir_i and rjr_j are similar so ωi,16=ωj,16    (1)si=sj\omega_{i,16} = \omega_{j,16} \stackrel{(1)}{\implies} s_i = s_j which is a contradiction. ■

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.