Search

U svakom vrhu pravilnog $n$-terokuta $A_1A_2\ldots A_n$ nalazi se određeni broj novčića: u vrhu $A_k$ nalazi se točno $k$ novčića, za svaki $k = 1, 2, \ldots, n$. U svakom koraku radimo sljedeću transformaciju: odabiremo dva novčića (ne nužno iz istog vrha) i prebacujemo svakog od njih u susjedni vrh, tako da jednog pomičemo u smjeru kretanja kazaljke na satu, a drugog u smjeru suprotnom od smjera kretanja kazaljke na satu.

Odredi za koje brojeve $n$ je moguće postići da nakon konačnog broja koraka za svaki $k = 1, 2, \ldots, n$ u vrhu $A_k$ bude točno $n + 1 - k$ novčića.

Neka polja pravokutne ploče $n \times m$ ($n, m \geqslant 2$) obojana su crnom bojom, dok su ostala polja bijela. Izvan ploče nalazi se žaba koja u jednom trenutku skoči na neko rubno polje ploče, a zatim radi niz skokova, skačući svaki put na neko od susjednih polja. (Za dva polja kažemo da su susjedna ako imaju zajedničku stranicu.) Svaki put kad žaba doskoči na neko polje, boja tog polja se mijenja, iz bijele u crnu ili obratno.

Postoji li put kojim žaba može proći i napustiti ploču skočivši s rubnog polja tako da nakon toga sva polja budu crne boje?

Na svakom polju ploče $n \times n$ ($n \geqslant 2$) nalazi se žarulja koja može biti upaljena ili ugašena.

U svakom koraku biramo jedan kvadrat $2 \times 2$ na toj ploči i unutar njega sve upaljene žarulje ugasimo, a ugašene upalimo. Za raspored upaljenih žarulja kažemo da je dobar ako se može postići da, počevši od njega, nakon konačno mnogo koraka, sve žarulje budu ugašene.

a) Dokaži da raspored prikazan na slici nije dobar. (Prikazan je položaj svih upaljenih žarulja na ploči $10 \times 10$.)

b) Koliko bi, u tom primjeru, minimalno dodatnih žarulja na početku trebalo upaliti da raspored bude dobar?

c) Odredi broj svih mogućih dobrih početnih rasporeda za $n \times n$ ploču.

Na nekoj zabavi među bilo koje četiri osobe postoje tri koje se sve međusobno poznaju ili postoje tri koje se međusobno ne poznaju. Poznanstva su uzajamna. Dokaži da se svi sudionici te zabave mogu smjestiti u dvije prostorije tako da se u jednoj prostoriji svi međusobno poznaju, a u drugoj nitko nikoga ne poznaje.

Dani su prirodni brojevi $M$ i $N$. Promatramo $N^2$ žarulja raspoređenih u tablicu s $N$ redaka i $N$ stupaca. Svaka žarulja može biti uključena ili isključena, a na početku su sve žarulje isključene.

Potez se sastoji od odabira bilo kojih $M$ uzastopnih žarulja u nekom retku ili stupcu te mijenjanja njihovog stanja, tako da svaka od odabranih $M$ žarulja koja je prije bila isključena, nakon poteza bude uključena, i obratno.

Ako je konačnim brojem poteza moguće postići da sve žarulje budu uključene, dokaži da je broj $M$ djelitelj broja $N$.

Svaka strana i svaka dijagonala nekog konveksnog $n$-terokuta obojana je u neku od $k$ boja. Poznato je da ne postoji jednobojna zatvorena izlomljena linija kojoj su vrhovi također i vrhovi danog mnogokuta. Kolika je najveća moguća vrijednost broja $n$?

Neka je $n \geq 3$ prirodan broj. Odredi minimalni broj točaka koje treba označiti unutar bilo kojeg konveksnog $n$-terokuta tako da svaki trokut kojem su vrhovi ujedno vrhovi tog $n$-terokuta sadrži u svojoj unutrašnjosti barem jednu označenu točku.

Svakom vrhu pravilnog mnogokuta pridružen je jedan od brojeva $0$ ili $1$. Koristeći dijagonale koje se međusobno ne sijeku osim u vrhovima, Rudi dijeli mnogokut na trokute, a zatim u svaki trokut upisuje zbroj brojeva pridruženih njegovim vrhovima. Dokaži da Rudi može odabrati dijagonale kojima će podijeliti mnogokut tako da se najveći i najmanji od brojeva upisanih u dobivene trokute razlikuju za najviše $1$.

U državi postoji $g$ gradova i $c$ cesta, pri čemu svaka cesta povezuje točno dva različita grada, a između dva grada postoji najviše jedna cesta. Ceste su označene brojevima $1, 2, \ldots, c$. Tonći svoje putovanje mora proći tako da kad zapiše oznake cesta redom kojim ih je prolazio dobije (strogo) rastući niz brojeva. Dokaži da postoji grad takav da krenuvši iz toga grada Tonći može proći barem $\dfrac{2c}{g}$ cesta.

Uz obalu nekog otoka nalazi se $20$ sela. U svakom selu živi $20$ boraca. Svaki od boraca bori se sa svim borcima iz ostalih sela. Svaka dva borca imaju različitu snagu i borac koji je snažniji pobjeduje u borbi. Kažemo da je selo $A$ nadvladalo selo $B$ ako je u barem $k$ borbi između boraca iz $A$ i boraca iz $B$ pobijedio borac iz $A$. Nakon svih borbi ustanovljeno je da je svako selo nadvladalo selo koje mu je neposredni susjed u smjeru kazaljke na satu.

Dokaži da najveći mogući $k$ iznosi $290$.

Neka je $A$ sedmeročlani podskup skupa $\{1,2,3,\ldots,26\}$. Dokaži da postoje dva različita neprazna podskupa od $A$ takva da su zbrojevi njihovih elemenata jednaki.

Na kružnicu stavljamo crvene i plave kuglice. Na početku se na kružnici nalaze samo dvije crvene kuglice. Dozvoljeni su sljedeći potezi:

i) dodati jednu crvenu kuglicu i promijeniti boju svake od dviju njoj susjednih kuglica (crvenu u plavu i obratno);

ii) maknuti jednu crvenu kuglicu i promijeniti boju svake od dviju njoj susjednih kuglica.

Možemo li nizom takvih poteza postići da na kružnici bude

a) $2013$ crvenih i $2013$ plavih kuglica;

b) samo dvije plave kuglice?

Dani su prirodni brojevi $N$ i $K$. Neki broj učenika je raspoređen u $N$ nepraznih grupa, a zatim su ti isti učenici preraspoređeni u $N + K$ nepraznih grupa. Dokaži da se u drugom rasporedu barem $K + 1$ učenika našlo u manjoj grupi od one u kojoj su bili u prvom rasporedu.

Grupa ljudi različitih visina pleše mađarski narodni ples na otvaranju natjecanja MEMO 2013 u Veszprému. Kažemo da je čovjek prosječan ako je viši od jednog svog susjeda i niži od drugog. (Ljudi su raspoređeni u krug i svaki čovjek ima točno dva susjeda.)

Ako je ukupan broj ljudi $N$, odredi sve moguće vrijednosti broja prosječnih ljudi.

Dan je prirodni broj $M \geqslant 3$. Kažemo da je pravilni mnogokut sjajno obojan ako su sve njegove stranice i dijagonale obojane u točno $M$ boja tako da ne postoje tri vrha tog mnogokuta koja određuju trokut čije su stranice obojane u točno dvije boje.

Neka je $N$ najveći prirodni broj takav da postoji sjajno obojani pravilni mnogokut s točno $N$ vrhova.

a) Dokaži da je $N \leqslant (M - 1)^2$.

b) Ako je $M - 1$ prosti broj, dokaži da postoji sjajno obojani pravilni mnogokut s točno $(M - 1)^2$ vrhova.

Neka je $N \geqslant 3$ neparni prirodni broj. Na početku se u svakom polju tablice $N \times N$ nalazi broj $0$. U pojedinom potezu biraju se dva polja koja imaju zajedničku stranicu i zatim se oba broja u tim poljima povećaju za $1$ ili se oba broja smanje za $1$.

Ako su nakon $K$ poteza zbrojevi brojeva u svakom retku i svakom stupcu tablice međusobno jednaki, dokaži da je $K$ paran broj.

Neka je $N$ prirodni broj. Stepenicama zovemo dio kvadratne ploče dimenzija $N \times N$ koji se sastoji od prvih $K$ polja u $K$-tom retku za $K = 1, 2, \ldots, N$. Na koliko je načina moguće razrezati stepenice na pravokutnike različitih površina koji se sastoje od polja dane ploče?

Za dani prirodni broj $n$ nađi najmanji prirodni broj $k$ sa sljedećim svojstvom:

Ako su $a_1, a_2, \ldots, a_d$ realni brojevi, $0 \leqslant a_i \leqslant 1$, $a_1 + a_2 + \cdots + a_d = n$, tada je moguće rasporediti tih $d$ brojeva u $k$ grupa tako da je zbroj brojeva u svakoj grupi najviše $1$ (neke grupe mogu biti prazne).

Dvadesetoro djece ima $100$ vrpci. Svaku vrpcu drže za krajeve dva djeteta. Dva djeteta mogu zajedno držati samo jednu vrpcu. Pretpostavimo da je par vrpci čija četiri kraja drže različita djeca moguće odabrati na $4050$ načina. Dokaži da svako dijete drži jednak broj vrpci.

Neka $m$ prirodni broj. Dano je $2^{m}$ papira i na svakom od njih napisan je broj $1$. U svakom potezu dozvoljeno je izabrati dva različita papira, pobrisati brojeve $a$ i $b$ koji pišu na tim papirima te na oba papira napisati broj $a + b$.

Dokaži da nakon $2^{m-1}m$ poteza zbroj brojeva na svim papirima iznosi najmanje $4^{m}$.

Dan je prirodni broj $N$. U svakom polju tablice $N \times N$ na početku je upisana nula. U svakom potezu dozvoljeno je odabrati redak ili stupac, obrisati sve brojeve koji se nalaze u njemu i upisati brojeve od $1$ do $N$ proizvoljnim redom. Koliko maksimalno može iznositi zbroj svih brojeva u tablici?

U nekoj državi je $N$ gradova, među nekima postoje (dvosmjerne) avionske linije. Svaki let povezuje točno dva grada. Nijedan grad nije povezan izravnim letovima sa svim ostalim gradovima. Poznato je da za svaka dva grada $A$ i $B$ postoji točno jedan način da se dođe iz $A$ u $B$ koristeći najviše dva leta. Dokaži da je $N - 1$ kvadrat prirodnog broja.

U konveksnom $N$-terokutu nacrtane su neke dijagonale. Za nacrtanu dijagonalu kažemo da je dobra ako se siječe s točno jednom od ostalih nacrtanih dijagonala (vrhove ne ubrajamo u sjecišta). Odredi najveći mogući broj dobrih dijagonala.

U ravnini je dan skup $A$ koji sadrži $2016$ točaka tako da nikoje četiri točke iz skupa $A$ ne leže na istom pravcu. Dokaži da je moguće odabrati podskup $B \subset A$ koji sadrži barem $63$ točke tako da nikoje tri točke iz skupa $B$ ne leže na istom pravcu.

Na ploči $N \times N$ ($N \geq 2$) dva su dijagonalno suprotna kutna polja obojana u crno, a sva ostala obojana su u bijelo. U jednom koraku odaberemo redak ili stupac i promijenimo boju svakom polju u tom retku ili stupcu iz crne u bijelu i obratno. Koji je najmanji dodatni broj polja koje na početku moramo obojati u crno kako bismo nakon konačnog broja opisanih koraka mogli dobiti ploču na kojoj su sva polja crna?

Dano je $N \geq 3$ točaka u ravnini takvih da nikoje tri ne leže na istom pravcu. Svaka dužina koja spaja dvije dane točke je obojana crvenom ili plavom bojom. Dokaži da postoji $N - 1$ dužina iste boje koje ne dijele ravninu na više od jednog dijela takve da se nikoje dvije ne sijeku osim u vrhovima.

Može li se ploča $12 \times 12$ popločati L-trominima tako da svaki redak i svaki stupac siječe isti broj tromina?

L-tromino se sastoji od tri jedinična kvadrata koja se ne nalaze u istom stupcu ili retku.

Dokaži da je moguće svaki prirodni broj obojiti jednom od tri boje tako da sljedeća dva uvjeta budu zadovoljena:

i) Za svaki $n \in \mathbb{N}_0$, svi prirodni brojevi $x$ takvi da je $2^n \leqslant x < 2^{n+1}$ su iste boje.

ii) Ne postoje prirodni brojevi $x, y$ i $z$ iste boje (osim $x = y = z = 2$) takvi da vrijedi $x + y = z^2$.

U jednoj organizaciji postoje tri odbora. Svaka osoba pripada točno jednom odboru. Za svake dvije osobe koje pripadaju različitim odborima, u preostalom odboru postoji točno $10$ osoba koje te dvije osobe obje poznaju, te točno $10$ osoba koje nijedna od te dvije osobe ne poznaje. Poznanstva su uzajamna. Koliko je ukupno osoba u sva tri odbora zajedno?

U nekom arhipelagu nalazi se $2017$ otoka nazvanih $1, 2, \ldots, 2017$. Dvije agencije, Crveni zmaj i Plavo oko, dogovaraju se oko rasporeda brodskih linija između pojedinih otoka. Za svaki par otoka, točno jedna agencija će organizirati brodsku liniju i to samo u smjeru od otoka nazvanog manjim brojem do otoka nazvanog većim brojem.

Raspored brodskih linija je dobar ako ne postoje dva otoka s oznakama $A < B$ takva da je s otoka $A$ na otok $B$ moguće doći koristeći samo brodove Crvenog zmaja, a također i koristeći samo brodove Plavog oka.

Odredi ukupan broj dobrih rasporeda brodskih linija.

Ludi lovac je figura koja može biti okrenuta prema jednom od četiri dijagonalno susjedna polja i napada sva polja ravno ispred sebe te ravno lijevo i desno od sebe (poput šahovskog lovca koji ne vidi iza sebe). Za dva polja igraće ploče kažemo da su dijagonalno susjedna ako imaju točno jedan zajednički vrh.

Odredi najveći prirodni broj $N$ za koji je na igraću ploču $8 \times 8$ moguće postaviti $N$ ludih lovaca tako da nijedan od njih ne napada nekog od ostalih.

Neka je $n$ prirodni broj. Dobra riječ je niz od $3n$ slova pri čemu se svako od slova $A$, $B$ i $C$ pojavljuje točno $n$ puta. Dokaži da za svaku dobru riječ $X$ postoji dobra riječ $Y$ takva da se $Y$ od $X$ ne može dobiti u manje od $\frac{3}{2}n^2$ zamjena susjednih slova.

Neka je $n$ prirodni broj. Unutar kružnice nalaze se točke $A_1, A_2, \ldots, A_n$, a na kružnici točke $B_1, B_2, \ldots, B_n$ takve da su dužine $\overline{A_1B_1}, \overline{A_2B_2}, \ldots, \overline{A_nB_n}$ u parovima disjunktne. Skakavac smije skočiti iz točke $A_i$ u točku $A_j$ (za $i, j \in \{1, \ldots, n\}$, $i \neq j$) ako i samo ako dužina $\overline{A_iA_j}$ ne prolazi nijednom unutarnjom točkom dužina $\overline{A_1B_1}, \overline{A_2B_2}, \ldots, \overline{A_nB_n}$.

Pokaži da skakavac nizom skokova može doći iz bilo koje točke $A_i$ u bilo koju točku $A_j$.

Na slici je prikazan lanac sastavljen od $54$ jedinična kvadratića. Svaki kvadratić, osim dvaju rubnih, spojen je s dva susjedna u nasuprotnim vrhovima.

Svaki kvadratić smije se postaviti u bilo koji položaj u prostoru uz uvjet da ostane spojen sa susjednim kvadratićima u odgovarajućim vrhovima. Je li moguće taj lanac postaviti tako da tvori oplošje kocke dimenzija $3 \times 3 \times 3$?

Neka je $a \geqslant 2018$ realni broj. U svakoj od $2018$ posuda nalazi se konačan broj kuglica, pri čemu je masa svake kuglice oblika $a^k$, gdje je $k \in \mathbb{Z}$. Ukupna masa kuglica u svakoj posudi je jednaka. Koliko se najmanje kuglica jednake mase pojavljuje među kuglicama u posudama?

Kriptogramom prirodnog broja $n$ zovemo uređenu $n$-torku $a = (a_1, a_2, \ldots, a_n)$ brojeva iz $\mathbb{N}_0$ takvu da vrijedi $$a_1 + 2a_2 + \cdots + na_n = n.$$

Neka je $\mathcal{K}_n$ skup svih kriptograma broja $n$. Za $a \in \mathcal{K}_n$ označimo sa $J(a)$ broj pojavljivanja broja $1$ u kriptogramu $a$. Dokaži da vrijedi $$\sum_{a \in \mathcal{K}_n} J(a) = \sum_{a \in \mathcal{K}_{n+1}} a_2.$$

Prerez konačnog skupa točaka u ravnini je podjela tog skupa na disjunktne podskupove $A$ i $B$, za koju postoji pravac koji ne prolazi niti jednom točkom promatranog skupa, takav da su sve točke skupa $A$ s jedne strane, a sve točke skupa $B$ s druge strane tog pravca. Odredi najveći mogući broj prereza skupa od $n$ točaka u ravnini.

Je li moguće ploču dimenzija $1000 \times 1000$ prekriti koristeći isključivo likove prikazane na slikama:

postavljene upravo na taj način? Likove nije dozvoljeno rotirati niti zrcaliti. Trebaju biti postavljeni tako da prekrivaju točno tri odnosno pet polja ploče i ne smiju se preklapati.

Ante je zapisao niz $a_1, a_2, \ldots, a_{2020}$ u kojem se svaki od brojeva $1, 2, \ldots, 2020$ pojavljuje točno jednom. Barbara želi saznati taj niz, a Ante joj daje informacije kroz niz razmjena.

U jednoj razmjeni Barbara na papir zapiše brojeve od $1$ do $2020$ te neke od njih spoji crtom i to tako da je svaki broj spojen s najviše jednim drugim i preda taj papir Anti. Ante zatim na drugi papir zapiše brojeve od $1$ do $2020$ te za svaki par brojeva $i$ i $j$ koje je Barbara spojila crtom, on spoji crtom brojeve $a_i$ i $a_j$, te na kraju preda taj papir Barbari.

Koliko je najmanje razmjena potrebno da Barbara može sa sigurnošću odrediti Antin niz?

Dano je $n$ cigli od kojih svaka ima masu barem $1$. Ukupna masa svih $n$ cigli je $2n$.

Dokaži da za svaki realni broj $r \in [0, 2n-2]$ možemo odabrati neke od tih cigli čija je ukupna masa u intervalu $[r, r+2]$.

Splet je konačan skup pravaca u općem položaju (tj. svaka dva pravca se sijeku, ali nikoja tri ne prolaze istom točkom). Pravci spleta dijele ravninu na područja čije su stranice dužine ili polupravci. Labirint je splet u kojem je svaki pravac obojan, poput zida, s jedne strane crvenom, a s druge strane plavom bojom. Dva područja sa zajedničkim vrhom koja u toj točki imaju i crvene i plave stranice nazivamo povezanima. Po labirintu se kreću mravi koji mogu prijeći iz područja u kojem se nalaze samo u područje koje je s njim povezano. Za splet $S$ definiramo $k(S)$ kao najveći broj mrava koje je moguće razmjestiti po svakom labirintu na $S$ tako da se nikoja dva mrava ne mogu sastati krećući se po labirintu.

Za $n \in \mathbb{N}$, odredi sve moguće vrijednosti $k(S)$ pri čemu je $S$ splet od $n$ pravaca.

Dan je jednakostraničan trokut na čijoj se svakoj stranici označeno po $9$ točaka koje dijele tu stranicu na $10$ sukladnih dijelova. Te su točke spojene s ukupno $27$ dužina paralelnih stranicama trokuta. Na taj način trokut je podijeljen na $100$ malih jednakostraničnih trokuta. Područje između dvije susjedne paralelne dužine nazivamo prugom.

Koliko najviše malih trokuta možemo odabrati tako da unutar nijedne pruge ne budu dva odabrana trokuta?

Na svakom polju ploče dimenzija $n \times n$ nalazi se po jedna žarulja. Na početku su neke žarulje upaljene, a neke ugašene. U svakom koraku biramo kvadrat $2 \times 2$ ili $3 \times 3$ te svim žaruljama u tom kvadratu promijenimo stanje (upaljene žarulje ugasimo, a ugašene upalimo).

Dokaži da za svaki prirodni broj $n$ postoji raspored žarulja koje ne možemo sve ugasiti konačnim nizom takvih koraka.

Pravilni mnogokut $\mathcal{P}$ ima $100$ vrhova od kojih je $41$ crne, a preostalih $59$ bijele boje.

Dokaži da postoje $24$ međusobno disjunktna konveksna četverokuta čiji su vrhovi vrhovi od $\mathcal{P}$ te svaki od njih ima neparan broj crnih vrhova.

Neka je $N$ prirodan broj i neka je $S = \{1, 2, \ldots, N\}$. Neka su $a_{i,j}$ međusobno različiti realni brojevi takvi da za sve $i, j \in S$ vrijedi: ako je $i < j$, onda je $$a_{i,k} < a_{j,k} \quad \text{i} \quad a_{k,i} < a_{k,j}, \quad \text{za sve} \quad k \in S.$$

Neka je $n$ prirodan broj takav da je $2(n-1)^2 < N$. Dokaži da postoje $n$-člani podskupovi $I, J \subset S$ takvi da vrijedi jedna od sljedeće dvije tvrdnje:

• za sve $i, k \in I$ vrijedi: ako je $i < k$, onda je $a_{i,j} < a_{k,l}$, za sve $j, l \in J$,

• za sve $j, l \in J$ vrijedi: ako je $j < l$, onda je $a_{i,j} < a_{k,l}$, za sve $i, k \in I$.

Za permutaciju $(a_1, a_2, \ldots, a_n)$ skupa $\{1, 2, \ldots, n\}$ kažemo da je uravnotežena ako vrijedi $$a_1 \leq 2a_2 \leq \ldots \leq na_n.$$

Neka $S(n)$ označava broj uravnoteženih permutacija skupa $\{1, 2, \ldots, n\}$.

Odredi $S(20)$ i $S(21)$.

Neka je $n \geqslant 3$ prirodan broj. Za prirodan broj $m \geqslant n + 1$ kažemo da je $n$-obojiv ako je $m$ kamenčića postavljenih na kružnici moguće obojati u $n$ boja tako da se među bilo kojih $n + 1$ uzastopnih kamenčića pojavljuje svih $n$ boja.

Dokaži da postoji konačno mnogo prirodnih brojeva $m \geqslant n + 1$ koji nisu $n$-obojivi i odredi najveći od njih.

Neka je $n$ prirodan broj. U grupi od $n$ ljudi, neki među njima su prijatelji, a neki nisu. Prijateljstva su uzajamna.

Grupa je posjetila vidovnjaka. Svaka od $n$ osoba rekla je vidovnjaku koliko ima prijatelja u grupi. Vidovnjak je nakon toga rekao da za svaki par osoba iz grupe može sa sigurnošću odrediti jesu li prijatelji ili ne.

Ako je vidovnjak rekao istinu, dokaži da u grupi ili postoji osoba koja je prijatelj sa svima ostalima, ili postoji osoba koja nije prijatelj ni s kim.

Neka je $n$ prirodan broj. U selu živi $2n$ ljudi. Neki među njima su su prijatelji, a prijateljstva su uzajamna. Savršeno sparivanje je podjela stanovnika sela na $n$ parova tako da su u svakom paru dvije osobe koje su prijatelji.

Pretpostavimo da u selu postoji točno jedno savršeno sparivanje. Koji je najveći mogući broj prijateljstava u selu?

Za prirodne brojeve $n$ i $k$, promatramo popločavanja ploče dimenzija $2n \times k$ dominima dimenzija $2 \times 1$. U jednom potezu je dopušteno izabrati $2 \times 2$ kvadrat na ploči koji je potpuno prekriven s dva domina, te okrenuti ga za $90°$ oko središta. Kažemo da su dva popločavanja ekvivalentna ako je od jednog moguće dobiti drugog primjenom konačno mnogo dopuštenih poteza. Za koje parove $(n, k)$ su sva popločavanja ekvivalentna?