MetaMath '22 - demo

Ukoliko se u nekom trenutku na istom polju nalazi više buba, primijetimo da ih možemo tretirati kao jednu bubu. Dokazati ćemo da je moguće dovesti sve bube na ploču $2 \times 2$ u lijevom gornjem kutu ploče. Primijetimo da za svaki $n>2$, sve bube iz polja $(k,n)$, $k>1$, mogu preći u polje $(k-1,n-1)$, dok buba iz polja $(1,n)$ može preći u polje $(2,n-1)$. Analogno, bube iz polja $(n,k), \, k>1$, mogu preći u polje $(n-1,k-1)$, dok buba iz polja $(n,1)$ može preći u polje $(n-1,2)$. Dakle, u jednom potezu možemo sve bube iz gornjeg lijevog kvadrata $n \times n$ dovesti u gornji lijevi kvadrat $(n-1) \times (n-1)$. Dakle, konačnim nizom poteza možemo dovesti bube iz početnog kvadrata $9 \times 9$ u gornji lijevi kvadrat $2 \times 2$. Time smo pokazali da bube možemo svesti na $4$ polja. Dokažimo da ne možemo manje od toga. Promatranjem parnosti koordinata polja na kojem se buba nalazi zaključujemo da se prilikom poteza događaju prijelazi: $$(PARNO, PARNO) \ \longrightarrow \ (NEPARNO, NEPARNO)$$ $$(PARNO, NEPARNO) \ \longrightarrow \ (NEPARNO, PARNO)$$ $$(NEPARNO, PARNO) \ \longrightarrow \ (PARNO, NEPARNO)$$ $$(NEPARNO, NEPARNO) \ \longrightarrow \ (PARNO, PARNO)$$ Kako na početku postoji barem $1$ buba na svakom od $4$ tipa polja po parnosti koordinata, primjećujemo da će i nakon svakog poteza uvijek postojati barem $1$ buba na svakom od tih tipova polja. Iz tog je razloga najmanji mogući broj upravo $4$.