INA PITALICA: Probajte riješiti pitanje koje nitko nije uspio

Nakon prve dvije INA pitalice u ovoj godini objavljujemo imena pobjednika i pobjednica. Zanimljivo je da nitko od prijavljenih natjecatelja nije uspio točno odgovoriti na INA pitalicu za mjesec veljaču, ali smo zato nagradili dvije osobe za točan odgovor u ožujku. Naši pobjednici su Stjepan Majdak i Biljana Ikić.

INA pitalica projekt je portala srednja.hr koji se realizira uz pomoć Mladih nadarenih matematičara Marin Getaldić (MNM). Od prijavljenih kandidata za pitalicu u veljaču nitko nije točno riješio mozgalicu, a vama savjetujemo da prije nego pročitate rješenje probate prvo sami rješiti zadatak.

INA pitalica za veljaču

U jednoj državi svi su gradovi bili
međusobno spojeni cestama (svaki grad sa svakim veže jedna, izravna
cesta). Nakon odluke kralja da se ceste privatiziraju, dvije su
kompanije, Alfa i Beta, otkupile ceste. Svaka je kompanija dobila neki
broj cesta. Kompanija Alfa cestama u svom vlasništvu ne može povezati
sve gradove. Možemo li iz toga zaključiti da kompanija Beta može
povezati sve gradove svojim cestama?

(Napomena; kompanija X
može povezati gradove znači da postoji put od jednog do drugog grada
korištenjem samo cesta u vlasništvu kompanije X)

Rješenje:

Možemo!

Pretpostavimo suprotno, da se ne mogu povezati svi gradovi. Tada postoje dva grada, nazovimo ih X i Y, koja se ne mogu povezati cestama kompanije Beta. Odatle slijedi da je izravna cesta između ta dva grada u vlasništvu kompanije Alfa. Budući da znamo kako Alfa ne može povezati sve gradove, postoji grad W koji se ne može povezati s X (a onda ni s Y). To znači da je izravna cesta od X do W, kao i ona od Y do W u vlasništvu kompanije Beta. Međutim, tada možemo povezati X i Y cestama u vlasništvu Beta, putem X -> W -> Y. Kontradikcija.

INA pitalica za ožujak

Kako u prethodnom mjesecu nismo imali
pobjednika, za mjesec ožujak odlučili smo nagraditi dvoje ljudi koji će
od INA-e dobiti poklon iznenađenja. Pobjednici su Stjepan Majdak i
Biljana Ikić

Pitanje: Koliko ima uređenih četvorki neparnih prirodnih brojeva (x,y,z,w) takvih da vrijedi x+y+z+w = 14?
A koliko ih ima takvih da vrijedi x+y+z+w= 2013? A koliko takvih da vrijedi x+y+z+w=2014?

Rješenje:

Za podzadatak b: ne postoji niti jedna takva četvorka jer je zbroj četiriju neparnih brojeva uvijek paran

Za podzadatke a i c:

Pokušajmo prvo odgovoriti na pitanje na koliko načina možemo od n
predmeta odabrati njih k.
– prvi predmet možemo odabrati na n načina, drugi na (n-1) … a k-ti na
(n-k+1) način. Međutim, nije nam bitan redoslijed nego samo koje smo
predmete odabrali. Zato cijeli izraz moramo podijeliti s brojem
permutacija skupa od k predmeta, tj k!. Taj broj označimo s C(n, k).Sada
pokušajmo odgovoriti na pitanje koliko ima četvorki cijelih brojeva
većih ili jednakih nuli čiji je zbroj fiksan broj t.

‘Promotrimo niz od t+3 bijele kuglice. Ako neke tri od njih obojamo u
crnu, dobili smo jednu četvorku (prvi broj je broj bijelih kuglica
prije prve crne, drugi je broj bijelih kuglica između prve i druge crne,
treći je broj kuglica između druge i treće crne, a četvrti je broj
bijelih kuglica nakon treće crne). Dakle, odgovor na naše pitanje
zapravo je broj načina na koji možemo odabrati tri kuglice od njih t+3.

A to znamo iz prethodnog koraka C(n+3, 3). Na kraju, kako bismo
odgovorili na pitanje samo s neparnim brojevima, prikažimo te brojeve
kao 2a+1, 2b+1, 2c+1, 2d+1, pri čemu su a, b,c, d cijeli brojevi veći
ili jednaki nuli. Sada postavimo jednadžbu (na primjer, za slučaj prvi
podzadatak)
2a+1+2b+1+2c+1+2d+1=14 odakle slijedi a+b+c+d=5

A to znamo izračunati po prethodnom koraku, radi se o broju C(5+3, 3) tj. 56.

Za treći podzadatak istim postupkom dobivamo 170191056.

napomena: ista su se rješenja mogla dobiti izradom programa koji izračunava te zbrojeve

Novu INA pitalica objavljujemo 28.4. na portalu!