Konji v štali 20x20 (27. okt. 2018 - 8. nov. 2019)
Zahteve zaključka
Odprto: sobota, 27. oktober 2018, 00.00
Rok za oddajo: petek, 23. november 2018, 23.59
Bojan želi na tablo 20x20 postaviti čimveč konjev, vendar vsaki njegovi izbiri prostega polja sledi Anita, ki na izbrano prosto polje postavi kamen. Koliko največ konjev lahko Bojan postavi na tablo, če se konji medsebojno ne smejo napadati (skačejo tako kot pri šahu), ne glede na to, kako izbira prosta polja za svoje kamne Anita?
Namig 1: Primer 3x3 bi morali hitro rešiti zaradi ene stare naloge o 4ih konjih. Ni
pretežko dognati, da se na tablo 3x3 oz. 4x4 ne da postavit več kot 4
konje (premislite sami). Tisti, ki jim programiranje ni tuje, bi lahko
našli odgovor tudi za tablo 5x5, a za velikost 20x20 kar tako le ne bo
šlo.
Namig 2: Če postavlja Bojan svoje konje na bela polja, mu Anita lahko nagaja tako, da počene enako (tudi ona postavlja svoje kamne na bela polja), vendar lahko Bojan na ta način postavi na tablo 100 konjev (oz. v splošnem vsaj \(n^2/4\)).