Egy nxn-es táblázat minden mezőjében egy-egy betű van. A táblázat bármely két sora különböző. Bizonyítsuk be, hogy a táblázatnak van olyan oszlopa, amelyet elhagyva a megmaradó táblázatnak sincs két egyező sora?

Tegyük fel indirekten, hogy bármely oszlopot elhagyva lesz két olyan sor, ami megegyezik - tehát ez a két oszlop eredetileg csak annak az oszlopnak megfelelő 'koordinátában' különbözött. Tehát minden oszlophoz hozzá tudunk rendelni egy (i,j) párt, hogy az i-edik és j-edik sor csak abban a koordinátában különbözik. Azt könnyű látni, hogy két különböző oszlophoz nem rendelhetjük ugyanazt a párt.

Most van n darab sorod és n darab párod, ebből következik, hogy lesz egy kör: tehát a soroknak egy olyan s_1,s_2,s_3,..,s_k részhalmaza, hogy az (s_1,s_2), (s_2,s_3),...(s_k-1,s_k),(s_k,s_1) párok. Tehát ha kiindulok az s_1 sorból, akkor az (s_1,s_2) párnak megfelelő koordinátában lévő betűt alkalmasan megváltoztatva az s_2 sort kapom, és így tovább, míg vissza nem érek az s_1 sorhoz.

De ilyen nem lehet, mert minden pár különböző koordinátához tartozik, tehát ha az s_1-nek pl. a 3-adik koordinátáját kell megváltoztatni, hogy az s_2 sort kapjam, akkor a kör folyamán később ezt a koordináta már nem változik, tehát nem juthatok vissza az s_1 sorhoz.

Remélem sikerült nagyjából értelmesen elmagyaráznom.