Neocijenjeno
23. veljače 2016. 13:32 (8 godine, 4 mjeseci)
Sakrij rješenje
Sakrij rješenje
Upozorenje: Ovaj zadatak još niste riješili!
Kliknite ovdje kako biste prikazali rješenje.
Kliknite ovdje kako biste prikazali rješenje.
Podijelimo tablicu na
kvadrata dimenzija
i uočimo da svaki od ovih kvadrata može sadržavati najviše 2 elementa skupa
: naime, svaki je od brojeva u tom skupu djeljiv s 2 ili 3, pa među svaka tri broja iz tog skupa možemo uvijek naći dva koja imaju zajednički djelitelj. Zato se tri broja iz tog skupa ne mogu naći u
kvadrata u kojemu sva četiri polja imaju jedan zajednički vrh.
Dakle, svaki od tih kvadrata sadrži barem dva elementa skupa
. Budući da takvih kvadrata ima
, u čitavoj se tablici članovi skupa
pojavljuju barem
puta. Sada prema Dirichletovom principu zaključujemo kako će se jedan broj iz tog skupa u tablici pojaviti barem
puta.
![n^2](/media/m/3/6/a/36a0dd5a7e7ff0e6bbc714e33ddb1d63.png)
![2\times2](/media/m/c/1/0/c10d8bf1fddb01ea5293452431d2fc51.png)
![\{2,3,4,6,8,9,10\}](/media/m/5/3/f/53fda4d25947a5b5a83d2806ad4f87b7.png)
![2\times2](/media/m/c/1/0/c10d8bf1fddb01ea5293452431d2fc51.png)
Dakle, svaki od tih kvadrata sadrži barem dva elementa skupa
![\{1,5,7\}](/media/m/3/e/f/3ef90c19def1cf22f5b1755f00ffbc1f.png)
![n^2](/media/m/3/6/a/36a0dd5a7e7ff0e6bbc714e33ddb1d63.png)
![\{1,5,7\}](/media/m/3/e/f/3ef90c19def1cf22f5b1755f00ffbc1f.png)
![2n^2](/media/m/b/d/b/bdba3c0944d0ab1031d8b1c04a24b53b.png)
![\frac{2n^2}{3}](/media/m/c/8/2/c825892797009e1398dfb55559d14f86.png)