Допустим противное: какой бы столбец мы ни вычеркнули, в оставшейся таблице найдётся хотя бы одна пара одинаковых строк. Рассмотрим $n$ «укороченных» таблиц, получающихся из данной, соответственно, вычёркиванием первого, второго, $\ldots$, $n$-го столбца. Отметим для каждой из этих таблиц одну пару одинаковых строк (длины $n-1$). Будем теперь считать, что строки исходной таблицы — это точки на плоскости, причём точки, соответствующие отмеченным парам строк в укороченных таблицах, попарно соединены. Мы получили картинку «$n$ точек — $n$ отрезков». Нетрудно доказать, что в такой картинке найдётся цикл — замкнутая ломаная с вершинами в некоторых из наших точек. Пусть эти вершины соответствуют строкам $A_1$, $A_2$, $\ldots$, $A_m$, и пусть отрезок $A_iA_{i+1}$ получается в результате вычёркивания столбца $B_i$ ($i=1$, 2, $\ldots$, $m-1$), а отрезок $A_mA_1$ — столбца $B_m$. Тогда в исходной таблице строки $A_1$ и $A_2$ отличаются только в столбце $B_1$, строки $A_2$ и $A_3$ — только в столбце $B_2$, $\ldots$, строки $A_{m-1}$ и $A_m$ — только в столбце $B_{m-1}$, так что в столбце $B_m$ во всех этих строках записано одно и то же число. Но это противоречит тому, что точки, соответствующие строкам $A_1$ и $A_m$, соединены (поскольку, по условию, все строки в исходной таблице различны, строки $A_1$ и $A_m$ должны отличаться в столбце $B_m$).
