Competition problem — Combinatorics

Library / /18 of 57

Combinatorics Difficulty 6.2 National olympiad Prove it Russia

A table consists of $n$ rows and 10 columns. Each cell of this table contains a digit (i.e. an integer from 0 to 9). It appears that for every row $A$ and every pair of columns $B$ and $C$ there exists a row that differs from $A$ exactly in columns $B$ and $C$ . Prove that $n \ge 512$ . (R. Karasev)

В каждой клетке таблицы, состоящей из 10 столбцов и $n$ строк, записана цифра. Известно, что для любой строки $A$ и любых двух столбцов найдётся строка, отличающаяся от $A$ ровно в этих двух столбцах. Докажите, что $n \ge 512$ . (Р. Карасёв)

Solution

Пусть $R_0$ — первая строка таблицы. Рассмотрим любой набор из чётного количества столбцов и пронумеруем их слева направо: $C_1, \dots, C_{2m}$ . Тогда в таблице есть строка $R_1$ , отличающаяся от $R_0$ ровно в столбцах $C_1$ и $C_2$ ; далее, есть строка $R_2$ , отличающаяся от $R_1$ ровно в столбцах $C_3$ и $C_4$ ; ...; наконец, есть строка $R_m$ , отличающаяся от $R_{m-1}$ ровно в столбцах $C_{2m-1}$ и $C_{2m}$ (если $m=0$ , то $R_m = R_0$ ).

Итак, строка $R_m$ отличается от $R_0$ ровно в столбцах $C_1, C_2, \dots, C_{2m}$ . Значит, строки $R_m$ , построенные по различным наборам столбцов, различны. Поскольку количество наборов из чётного числа столбцов равно $2^{10}/2 = 512$ , то и количество строк в таблице не меньше 512.

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.