Croatian Mathematical Olympiad

U trokutu $ABC$ vrijedi $|AB| \neq |AC|$ i upisana kružnica dira stranice $\overline{BC}$, $\overline{AC}$ i $\overline{AB}$ redom u točkama $D$, $E$ i $F$. Okomica iz točke $D$ na pravac $EF$ sijeće stranicu $\overline{AB}$ u točki $G$, a kružnice opisane trokutima $AEF$ i $ABC$ se sijeku u točkama $A$ i $T$.

Dokaži da su pravci $TG$ i $TF$ okomiti.

Neka je $a_1, a_2, a_3, \ldots$ beskonačan niz brojeva iz skupa $\{1, 2, 3, 4, 5, 6, 7, 8\}$ takav da za svaki par prirodnih brojeva $(m, n)$ vrijedi:

uvjeti $a_n | n$ i $a_m | m$ ispunjeni su ako i samo ako je $a_{m+n} = a_m + a_n - 1$.

Odredi sve vrijednosti koje može poprimiti $a_{5555}$.

Neka je $\mathbb{R}^+$ skup svih pozitivnih, a $\mathbb{R}_0^+$ skup svih nenegativnih realnih brojeva.

Odredi sve funkcije $f: \mathbb{R}^+ \to \mathbb{R}_0^+$ takve da za sve pozitivne realne brojeve $x$ i $y$ vrijedi

$$f(x) - f(x + y) = f(x^2 f(y) + x).$$

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 $ABC$ raznostraničan šiljastokutan trokut. Točka $N$ je polovište duljeg luka $\widehat{BC}$ kružnice opisane trokutu $ABC$. Neka je $k$ kružnica promjera $\overline{BC}$.

Simetrala kuta $\measuredangle BAC$ siječe kružnicu $k$ u točkama $D$ i $E$, a $D_1$ i $E_1$ su točke takve da su $\overline{DD_1}$ i $\overline{EE_1}$ promjeri kružnice $k$.

Dokaži da polovište dužine $\overline{BC}$ pripada kružnici opisanoj trokutu $NE_1D_1$.

Označimo s $\tau(k)$ broj pozitivnih djelitelja prirodnog broja $k$, a s $\varphi(k)$ broj prirodnih brojeva koji nisu veći od $k$, a relativno su prosti s $k$. Za prirodan broj $m$ kažemo da je lijep ako postoji prirodan broj $n$ takav da vrijedi

$$\frac{\tau(m)}{m} = \frac{\varphi(n)}{n}.$$

Postoji li beskonačno mnogo lijepih brojeva?

Neka je $\mathbb{Q}_0^+$ skup svih nenegativnih racionalnih brojeva.

Odredi sve funkcije $f: \mathbb{Q}_0^+ \to \mathbb{Q}_0^+$ takve da za sve nenegativne racionalne brojeve $x$, $y$ vrijedi

$$yf(x + y) + (y - 1)f(xy) = f(y^2)f(x + 1).$$

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?

Neka je $ABCD$ paralelogram takav da je $|AC| = |BC|$. Neka je $P$ točka na pravcu $AB$ takva da $B$ leži između $A$ i $P$. Opisana kružnica trokuta $ACD$ siječe dužinu $\overline{PD}$ u točki $Q$, $Q \neq D$. Opisana kružnica trokuta $APQ$ siječe dužinu $\overline{PC}$ u točki $R$, $R \neq P$.

Dokaži da se pravci $CD$, $AQ$ i $BR$ sijeku u jednoj točki.

Odredi sve trojke prirodnih brojeva $(p, m, n)$ takve da je $p$ prost, $m < n$, sa svojstvom da postoje prirodni brojevi $a$, $b$, $c$, $d$ koji nisu djeljivi s $p$ takvi da vrijedi

$$\begin{aligned} ab + cd &= p^m, \\ ac + bd &= p^n. \end{aligned}$$

Neka su $a$, $b$ i $c$ pozitivni realni brojevi za koje vrijedi $ab + bc + ca = 1$.

Dokaži da je $$\frac{4}{a + b + c} \leq (a + b)(c\sqrt{3} + 1).$$

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.

Neka je $ABCD$ konveksni četverokut u kojem je $\measuredangle B > 90°$, $\measuredangle D > 90°$ te $\measuredangle A = \measuredangle C$. Neka su $E$ i $F$ redom točke osnosimetrične točki $A$ u odnosu na pravce $BC$ i $CD$. Neka dužine $\overline{AE}$ i $\overline{AF}$ sijeku pravac $BD$ redom u točkama $K$ i $L$.

Dokaži da se kružnice opisane trokutima $BKE$ i $FLD$ diraju.

Za svaki prost broj $p$ negdje u svemiru postoji planet $\mathcal{P}_p$ u čijem se oceanu nalazi točno $p$ otoka, $O_1, O_2, \ldots, O_p$. Između otoka $O_m$ i $O_n$ (za $m \neq n$) postoji most ako i samo ako je broj $(m^2 - n + 1)(n^2 - m + 1)$ djeljiv s $p$. S mosta nije moguće prijeći direktno na drugi most već samo na otok.

Dokaži da postoji beskonačno mnogo prostih brojeva $p$ za koje na planetu $\mathcal{P}_p$ nije moguće sa svakog otoka doći na svaki drugi krećući se samo po otocima i mostovima.

Odredi sve polinome $P$ s realnim koeficijentima takve da izraz $$P(x + 3y) + P(3x - y)$$ ima istu vrijednost za sve realne brojeve $x$, $y$ za koje je $x^2 + y^2 = 1$.

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.

Dan je trokut $ABC$ takav da je $|AC| = |BC|$ i točka $D$ na stranici $\overline{AB}$ takva da je $|AD| < |BD|$. Točke $P$ i $Q$ su redom nožišta okomica iz točke $D$ na stranice $\overline{AC}$ i $\overline{BC}$. Simetrala dužine $\overline{PQ}$ siječe $\overline{CP}$ u točki $E$. Kružnice opisane trokutima $ABC$ i $PQC$ sijeku se u točkama $C$ i $F$.

Ako su točke $E$, $F$ i $Q$ kolinearne, dokaži da je $\measuredangle ACB$ pravi kut.

Odredi sve parove $(a,b)$ prirodnih brojeva za koje vrijedi $$a^5 + a^4 = 7^b - 1.$$

Odredi sve realne brojeve $a$ za koje postoji funkcija $f: \mathbb{R} \to \mathbb{R}$ takva da je $$f(x + f(y)) = f(x) + a\lfloor y\rfloor,$$ za sve realne brojeve $x$ i $y$.

Napomena: $\lfloor y\rfloor$ je najveći cijeli broj koji nije veći od $y$. Npr. $\lfloor 1.7\rfloor = 1$, $\lfloor -\pi \rfloor = -4$, $\lfloor 0\rfloor = 0$.

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$.

Dan je konveksan četverokut $ABCD$ čije se dijagonale sijeku u točki $P$. Neka su $X$ i $Y$ točke odabrane tako da četverokuti $ABPX$, $CDXP$, $BCPY$ i $DAYP$ budu tetivni. Pravci $AB$ i $CD$ sijeku se u točki $Q$, pravci $BC$ i $DA$ u točki $R$, a pravci $XR$ i $YQ$ u točki $Z$. Dokaži da točke $X$, $Y$, $Z$ i $P$ pripadaju istoj kružnici.

Funkcija $U: \mathbb{N} \to \mathbb{N}$ definira se na sljedeći način: $$U(n) = \begin{cases} 1, & \text{za } n = 1, \\ \alpha_1^{p_1} \cdots \alpha_k^{p_k}, & \text{za } n = p_1^{\alpha_1} \cdots p_k^{\alpha_k}, \text{gdje su } p_1, \ldots, p_k \text{ međusobno različiti prosti brojevi i } \alpha_1, \ldots, \alpha_k \in \mathbb{N}. \end{cases}$$

Za $m \in \mathbb{N}$ neka je $U^{(m)}(n) = U(U(\ldots U(n)\ldots))$, pri čemu se $U$ primjenjuje $m$ puta.

Dokaži da za svaki prirodni broj $A$ postoji prirodni broj $B$ takav da je $U^{(m)}(A) = B$ za beskonačno mnogo prirodnih brojeva $m$.

Neka je $f: \mathbb{R} \to \mathbb{R}$ funkcija sa svojstvima:

(a) Postoji realan broj $M$ takav da je $|f(x)| \leq M$, za sve $x \in \mathbb{R}$.

(b) Za svaki realan broj $x$ vrijedi $$f\left(x + \frac{1}{2}\right) + f\left(x + \frac{1}{3}\right) = f(x) + f\left(x + \frac{5}{6}\right).$$

Pokaži da je funkcija $f$ periodična, odnosno da postoji pozitivan realan broj $T$ takav da je $f(x + T) = f(x)$ za sve $x \in \mathbb{R}$.

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 $ABCD$ konveksni četverokut čije se dijagonale sijeku u točki $E$. Pravci $AB$ i $CD$ sijeku se u točki $P$, a pravci $AD$ i $BC$ u točki $Q$. Neka je $X$ sjecište kružnica opisanih trokutima $EBC$ i $EDA$ različito od $E$, a $Y$ sjecište kružnica opisanih trokutima $EAB$ i $ECD$ različito od $E$. Konačno, neka je $W$ sjecište kružnica opisanih trokutima $PBC$ i $PDA$ različito od $P$. Dokaži da su trokuti $WQY$ i $WXP$ slični.

Neka $d(n)$ označava broj pozitivnih djelitelja broja $n$, a $s(n)$ zbroj svih pozitivnih djelitelja broja $n$. Odredi sve prirodne brojeve $n$ za koje je $$4s(n) = 3d(n)^2 + 1.$$

Neka je $n$ prirodni broj i neka su $x_1, x_2, \ldots, x_n$ realni brojevi takvi da je $$x_1 + x_2 + \cdots + x_n = 0 \quad \text{i} \quad x_1^2 + x_2^2 + \cdots + x_n^2 = 1.$$

Ako je $a$ najmanji, a $b$ najveći broj među brojevima $x_1, x_2, \ldots, x_n$, dokaži da je $ab \leq -\dfrac{1}{n}$.

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?

Dan je trokut $ABC$ takav da je $|AB| < |AC|$. Na stranicama $\overline{AB}$ i $\overline{BC}$, redom su dane točke $P$ i $Q$ takve da su pravci $AQ$ i $CP$ okomiti, a kružnica upisana trokutu $ABC$ dira dužinu $\overline{PQ}$. Pravac $CP$ siječe kružnicu opisanu trokutu $ABC$ u točkama $C$ i $T$.

Ako se pravci $CA$, $PQ$ i $BT$ sijeku u jednoj točki, dokaži da je kut $\measuredangle CAB$ pravi.

Za prirodni broj kažemo da je neobičan ako je zbroj recipročnih vrijednosti svih njegovih pozitivnih djelitelja različit od zbroja recipročnih vrijednosti svih pozitivnih djelitelja bilo kojeg drugog prirodnog broja.

(a) Dokaži da su svi prosti brojevi neobični.

(b) Dokaži da postoji beskonačno mnogo prirodnih brojeva koji nisu neobični.

Odredi sve funkcije $f: \mathbb{R} \to \mathbb{R}$ takve da za sve $x, y \in \mathbb{R}$ vrijedi $$f(x + yf(x)) = f(xf(y)) - x + f(y + f(x)).$$

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]$.

Dana je kružnica promjera $\overline{AB}$. Na toj kružnici, s različitih strana pravca $AB$, nalaze se točke $C$ i $D$ takve da vrijedi $|AC| < |BC|$ i $|AC| < |AD|$. Točka $P$ pripada dužini $\overline{BC}$ te vrijedi $\measuredangle CAP = \measuredangle ABC$. Okomica iz točke $C$ na pravac $AB$ siječe pravac $BD$ u točki $Q$. Pravci $PQ$ i $AD$ sijeku se u točki $R$, a pravci $PQ$ i $CD$ u točki $T$.

Ako je $|AR| = |RQ|$, dokaži da su pravci $AT$ i $PQ$ međusobno okomiti.

Skup $A \subset \mathbb{N}$ zovemo neprijateljskim ako za svaki par $(a,b)$ brojeva iz $A$ postoji $k \in \mathbb{N}_0$ takav da je $M(a,b) = 2^k$. Postoji li beskonačan skup $S \subset \mathbb{N}$ sa svojstvom da je skup svih mogućih zbrojeva dvaju različitih elemenata skupa $S$ neprijateljski skup?

Neka je $n \geq 3$ prirodni broj i neka je $(a_1, a_2, \ldots, a_n)$ strogo rastući niz realnih brojeva takav da je $\sum_{k=1}^n a_k = 2$. Neka je $M$ neki podskup skupa $\{1, 2, \ldots, n\}$ za koji je vrijednost izraza $\left|1 - \sum_{k \in M} a_k\right|$ najmanja moguća.

Dokaži da postoji strogo rastući niz realnih brojeva $(b_1, b_2, \ldots, b_n)$ takav da je $\sum_{k=1}^n b_k = 2$, za koji vrijedi $\sum_{k \in M} b_k = 1$.

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.

Neka je $ABC$ šiljastokutni trokut i neka su $D$, $E$ i $F$ nožišta njegovih visina iz vrhova $A$, $B$ i $C$, redom. Neka su $k_B$ i $k_C$ kružnice upisane trokutima $BDF$ i $CDE$, redom. Kružnica $k_B$ dodiruje dužinu $\overline{DF}$ u točki $M$, a kružnica $k_C$ dužinu $\overline{DE}$ u točki $N$. Pravac $MN$ siječe kružnicu $k_B$ u točkama $M$ i $P$, a kružnicu $k_C$ u točkama $N$ i $Q$.

Dokaži da je $|MP| = |NQ|$.

Dan je prirodni broj $C$. Odredi sve funkcije $f: \mathbb{N} \to \mathbb{N}$ sa sljedećim svojstvom:

za sve $a, b \in \mathbb{N}$ za koje je $a + b > C$, vrijedi $a + f(b) \mid a^2 + bf(a)$.

Odredi sve periodične nizove $(x_n)_{n \in \mathbb{N}}$ pozitivnih realnih brojeva sa svojstvom da za sve $n \in \mathbb{N}$ vrijedi $$x_{n+2} = \frac{1}{2}\left(\frac{1}{x_{n+1}} + x_n\right).$$

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?

Neka je $ABC$ trokut. Kružnica $k$ prolazi točkom $A$, siječe stranice $\overline{AB}$ i $\overline{AC}$ redom u točkama $D$ i $E$ (različitim od $A$), a stranicu $\overline{BC}$ u točkama $F$ i $G$ i pritom je $F$ između $B$ i $G$. Tangenta opisane kružnice trokuta $BDF$ u točki $F$ i tangenta opisane kružnice trokuta $CEG$ u točki $G$ sijeku se u točki $T$, različitoj od $A$.

Dokaži da su pravci $AT$ i $BC$ međusobno paralelni.

Funkcija $f: \mathbb{N}_0 \to \mathbb{N}_0$ je pseudopolinom ako za svaka dva različita broja $a, b \in \mathbb{N}_0$ vrijedi $$a - b \mid f(a) - f(b).$$

Odredi sve pseudopolinome takve da za svaki $n \in \mathbb{N}_0$ vrijedi $f(n) \leq n\sqrt{n}$.

Direktori dviju tvrtki nalaze se u točkama udaljenim $1000$ kilometara. U $n$ točaka na dužini između njih nalazi se po jedan matematičar. Svake sekunde u istom trenutku, svi matematičari se premještaju – svaki ide na polovište dužine koja spaja njega i njemu najbližu osobu (matematičara ili direktora). Ako takva osoba nije jedinstvena, po volji bira jednu od njih. Ako na taj način dva matematičara dođu u istu točku, mlađi od njih zauvijek odlazi.

Dokaži da će se, nakon konačno mnogo sekundi, svaki od preostalih matematičara moći rukovati s jednim od direktora. Matematičar se može rukovati s direktorom ako je od njega udaljen za najviše $1$ metar.

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.$$

Dan je jednakokračan trokut $ABC$ takav da je $|AB| = |AC|$. Neka je $M$ polovište stranice $\overline{BC}$ te neka je $P$ točka različita od $A$ takva da je $PA \parallel BC$. Točke $X$ i $Y$ nalaze se redom na polupravcima $PB$ i $PC$, tako da je točka $B$ između $P$ i $X$, točka $C$ između $P$ i $Y$ te vrijedi $\measuredangle PXM = \measuredangle PYM$. Dokaži da su točke $A$, $P$, $X$ i $Y$ konciklične.

Odredi sve prirodne brojeve $n$ takve da je $$\frac{n^{3n-2} - 3n + 1}{3n - 2}$$ cijeli broj.

Neka su $a$, $b$ i $c$ pozitivni realni brojevi. Dokaži da vrijedi $$\frac{\sqrt{a + b + c} + \sqrt{a}}{b + c} + \frac{\sqrt{a + b + c} + \sqrt{b}}{c + a} + \frac{\sqrt{a + b + c} + \sqrt{c}}{a + b} \geq \frac{9 + 3\sqrt{3}}{2\sqrt{a + b + c}}.$$

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.

Na stranici $\overline{AB}$ tetivnog četverokuta $ABCD$ postoji točka $X$ sa svojstvom da dijagonala $\overline{BD}$ raspolavlja dužinu $\overline{CX}$, a dijagonala $\overline{AC}$ raspolavlja dužinu $\overline{DX}$.

Koliki je najmanji mogući omjer $|AB| : |CD|$ u takvom četverokutu?

Neka je $f: \mathbb{N} \to \mathbb{N}$ multiplikativna funkcija takva da je $f(4) = 4$ i vrijedi $$f(m^2 + n^2) = f(m^2) + f(n^2) \quad \text{za sve } m, n \in \mathbb{N}.$$

Dokaži da je $f(m^2) = m^2$ za sve $m \in \mathbb{N}$.

Za funkciju $f$ kažemo da je multiplikativna ako za svaki izbor relativno prostih prirodnih brojeva $m$ i $n$ vrijedi $f(mn) = f(m)f(n)$.