Weboldalunk cookie-kat használhat, hogy megjegyezze a belépési adatokat, egyedi beállításokat, továbbá statisztikai célokra és hogy a személyes érdeklődéshez igazítsa hirdetéseit. További információ
Kezdőoldal » Tudományok » Természettudományok » Egy nxn-es táblázat minden...

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?

Figyelt kérdés

2016. márc. 20. 10:52
 1/2 anonim ***** válasza:

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.

2016. márc. 22. 20:08
Hasznos számodra ez a válasz?
 2/2 A kérdező kommentje:
Köszi!
2016. márc. 26. 16:25

Kapcsolódó kérdések:





Minden jog fenntartva © 2020, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | WebMinute Kft. | Facebook | Kapcsolat: info@gyakorikerdesek.hu

A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik.
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!