Search

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.

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.

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.

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.

Čarobna triangulacija je podjela trokuta na manje trokute konačnim brojem dužina čiji su krajevi vrhovi trokuta ili točke u njegovoj unutrašnjosti, pri čemu se u svakoj od tih točaka (uključujući vrhove trokuta) sastaje jednak broj dužina.

Na koliko najviše manjih trokuta trokut može biti podijeljen čarobnom triangulacijom?

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.

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.

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.

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

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.

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.

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?

Seventeen people correspond by mail with one another - each one with all the rest. In their letters only three different topics are discussed. Each pair of correspondents deals with only one of these topics. Prove that there are at least three people who write to each other about the same topic.

Suppose $G$ is a connected graph with $k$ edges. Prove that it is possible to label the edges $1, 2, \ldots, k$ in such a way that at each vertex which belongs to two or more edges, the greatest common divisor of the integers labeling those edges is equal to 1.

[A graph consists of a set of points, called vertices, together with a set of edges joining certain pairs of distinct vertices. Each pair of vertices $u, v$ belongs to at most one edge. The graph $G$ is connected if for each pair of distinct vertices $x, y$ there is some sequence of vertices $x = v_0, v_1, v_2, \ldots, v_m = y$ such that each pair $v_i, v_{i+1}$ ($0 \leq i < m$) is joined by an edge of $G$.]

In a mathematical competition some competitors are friends. Friendship is always mutual. Call a group of competitors a clique if each two of them are friends. (In particular, any group of fewer than two competitors is a clique.) The number of members of a clique is called its size.

Given that, in this competition, the largest size of a clique is even, prove that the competitors can be arranged in two rooms such that the largest size of a clique contained in one room is the same as the largest size of a clique contained in the other room.

A social network has 2019 users, some pairs of whom are friends. Whenever user $A$ is friends with user $B$, user $B$ is also friends with user $A$. Events of the following kind may happen repeatedly, one at a time:

Three users $A$, $B$, and $C$ such that $A$ is friends with both $B$ and $C$, but $B$ and $C$ are not friends, change their friendship statuses such that $B$ and $C$ are now friends, but $A$ is no longer friends with $B$, and no longer friends with $C$. All other friendship statuses are unchanged.

Initially, 1010 users have 1009 friends each, and 1009 users have 1010 friends each. Prove that there exists a sequence of such events after which each user is friends with at most one other user.

There is an integer $n > 1$. There are $n^2$ stations on a slope of a mountain, all at different altitudes. Each of two cable car companies, $A$ and $B$, operates $k$ cable cars; each cable car provides a transfer from one of the stations to a higher one (with no intermediate stops). The $k$ cable cars of $A$ have $k$ different starting points and $k$ different finishing points, and a cable car which starts higher also finishes higher. The same conditions hold for $B$. We say that two stations are linked by a company if one can start from the lower station and reach the higher one by using one or more cars of that company (no other movements between stations are allowed).

Determine the smallest positive integer $k$ for which one can guarantee that there are two stations that are linked by both companies.

Let $n\geq 3$ be an integer. At a MEMO-like competition, there are $3n$ participants, there are $n$ languages spoken, and each participant speaks exactly three different languages.

Prove that at least $\left\lceil\dfrac{2n}{9}\right\rceil$ of the spoken languages can be chosen in such a way that no participant speaks more than two of the chosen languages.

($\lceil x\rceil$ is the smallest integer which is greater than or equal to $x$.)

Let $n$ be a positive integer. In the province of Laplandia there are $100n$ cities, each two connected by a direct road, and each of these roads has a toll station collecting a positive amount of toll revenue. For each road, the revenue of its toll station is split equally between the two cities at the ends of the road (meaning that each of the two cities receives half of the income). For each city, the total toll revenue is given by the sum of the revenues it receives from the $100n - 1$ toll stations on its roads.

According to a new law, the revenues of some of the toll stations will be collected by the federal government instead of by the adjacent cities. The governor of Laplandia is allowed to choose those toll stations. The mayors of the cities demand that for each city, the sum of the remaining revenues it receives from the other toll stations after this change is at least $99\%$ of its former total toll revenue.

Find the largest positive integer $k$, depending on $n$, such that the governor can always choose $k$ toll stations for the federal government to collect the toll revenue, while satisfying the demand of the city mayors.

Supružnici Ana i Tomislav došli su na zabavu na kojoj su sudjelovala još četiri para. Prilikom dolaska dogodio se izvjestan broj rukovanja. Pritom se nitko nije rukovao sa svojim bračnim drugom niti sa samim sobom. Kada je kasnije Tomislav upitao sve prisutne s koliko su se osoba rukovali, dobio je devet različitih odgovora. S koliko se osoba rukovala Ana?

Dan je konveksan mnogokut s 2022 vrha kojem se nikoje tri dijagonale ne sijeku u istoj točki. Potrebno je obojiti neke dijagonale crveno tako da iz svakog vrha izlazi barem jedna crvena dijagonala.

Koliko je najmanji mogući broj sjecišta (u vrhu ili unutrašnjosti) crvenih dijagonala?

U jednom gradu je $M$ ulica i $N$ trgova, pri čemu su $M$ i $N$ prirodni brojevi takvi da je $M > N$. Svaka ulica povezuje dva trga i ne prolazi kroz druge trgove.

Gradani žele promijeniti izgled grada. Ove godine svaka će ulica biti po prvi put obojena crveno ili plavo. Dogovoreno je da se svake godine odabere jedan trg, te svim ulicama koje vode do tog trga istovremeno promijeni boja iz plave u crvenu i obratno.

Dokaži da građani mogu odabrati boje ulica tako da se nikad u budućnosti ne može dogoditi da sve ulice budu iste boje.

Na slici je prikazan skup od $16$ točaka raspoređenih na $10$ istaknutih pravaca. Za dvije točke tog skupa kažemo da su vezane ako pripadaju istom istaknutom pravcu.

a) Koliko je najviše točaka promatranog skupa moguće odabrati tako da među njima ne bude vezanih točaka?

b) Odredi broj podskupova promatranog skupa točaka bez vezanih točaka s najvećim mogućim brojem elemenata.

Polja ploče $2 \times 50$ potrebno je obojati u dvije boje, crvenu i plavu, tako da budu zadovoljeni sljedeći uvjeti:

• na ploči se pojavljuju obje boje
• uklanjanjem svih crvenih polja ploča ostaje povezana
• uklanjanjem svih plavih polja ploča ostaje povezana.

Ploča je povezana ako se od svakog polja može doći do svakog drugog, prelazeći u svakom koraku s polja na njemu susjedno polje. Polja su susjedna ako imaju zajedničku stranicu.

Na koliko je načina to moguće napraviti?

Na nekom turističkom putovanju bilo je ukupno $17$ turista. Utvrđeno je da su bilo koja dvojica od njih bili međusobno "na ti" ili "na vi" ili uopće nisu razgovarali. Dokažite da među tih $17$ ljudi postoje bar trojica koji su međusobno bili "na ti" ili bar trojica koji su međusobno bili "na vi" ili bar trojica koji međusobno nisu razgovarali.

Na otoku živi $n$ domorodaca. Svaka dva su ili prijatelji ili neprijatelji. Jednog dana poglavica naredi svim stanovnicima (uključujući i sebe) da si naprave i da nose kamene ogrlice, tako da svaka dva prijatelja imaju barem po jedan istovrsni kamen u svojim ogrlicama, a da se sva kamenja u ogrlicama dvaju neprijatelja razlikuju. (Ogrlica može biti i bez kamenja.) Dokažite da se poglavičina zapovijed može izvršiti koristeći $\left\lfloor \dfrac{n^2}{4} \right\rfloor$ različitih vrsta kamenja, i da se općenito ovo ne može postići s manje kamenja.

Šest otoka povezano je linijama jednog trajektnog i jednog hidrogliserskog poduzeća. Svaka dva otoka povezana su (u oba smjera) linijom točno jednog od ova dva poduzeća. Dokaži da je moguće ciklički posjetiti četiri otoka koristeći linije samo jednog poduzeća (tj. da postoje četiri otoka $A$, $B$, $C$ i $D$ i poduzeće čiji brodovi plove na linijama $A \leftrightarrow B$, $B \leftrightarrow C$, $C \leftrightarrow D$, $D \leftrightarrow A$).

U nekoj državi između svaka dva grada postoji ili izravna autobusna ili izravna željeznička veza (sve veze su dvosmjerne i ne prolaze ni kroz jedan drugi grad).

Dokaži da je gradove u toj državi moguće rasporediti u dva disjunktna skupa tako da je sve gradove u jednom skupu moguće obići putujući samo željeznicom tako da se nijedan grad ne posjeti dvaput, a sve gradove u drugom skupu putujući samo autobusom tako da se nijedan grad ne posjeti dvaput.

U nekom arhipelagu je $n$ otoka među kojima prometuju dvosmjerne brodske i avionske linije. Između svaka dva otoka postoji točno jedna direktna linija – ili brodka, ili avionska. Kažemo da je arhipelag uredno povezan ako svako kružno turističko putovanje koje počinje i završava na istom otoku koristi paran broj avionskih linija.

Za koje prirodne brojeve $n$ svaki uredno povezan arhipelag s $n$ otoka ima paran broj avionskih linija?

U ravnini je dano osam točaka koje su vrhovi pravilnoga osmerokuta. Svake dvije točke spojene su dužinom. U svakome potezu odabiru se tri točke te se brišu tri dužine kojima su te točke krajnje. Koliki je najmanji mogući broj preostalih dužina u trenutku kad nije više moguće napraviti takav potez?

Šest otoka povezano je linijama jednog trajektnog i jednog hidrogliserskog poduzeća. Svaka dva otoka povezana su (u oba smjera) linijom točno jednog od ova dva poduzeća. Dokaži da je moguće ciklički posjetiti četiri otoka koristeći linije samo jednog poduzeća (tj. da postoje četiri otoka $A$, $B$, $C$ i $D$ i poduzeće čiji brodovi plove na linijama $A \leftrightarrow B$, $B \leftrightarrow C$, $C \leftrightarrow D$, $D \leftrightarrow A$).

Na natjecanju sudjeluje 300 natjecatelja. Svaka dva natjecatelja se međusobno ili poznaju ili ne poznaju, a ne postoje tri natjecatelja koji se svi međusobno poznaju. Odredi najveću moguću vrijednost broja $n$ tako da vrijede sljedeći uvjeti:

• Svaki natjecatelj poznaje najviše $n$ ostalih natjecatelja.

• Za svaki prirodni broj $m$ takav da je $1 \leqslant m \leqslant n$ postoji barem jedan natjecatelj koji poznaje točno $m$ ostalih natjecatelja.

Za arhipelag od 2026 otoka kažemo da je dobro povezan ako među svakih pet različitih otoka, postoje tri takva da između svaka dva od njih postoji dvosmjerna brodska linija. Odredi najveći prirodni broj $N$ takav da u svakom dobro povezanom arhipelagu postoji niz od barem $N$ različitih otoka takav da su svaka dva uzastopna, te prvi i posljednji otok u nizu povezani brodskom linijom.

U prostoriji se nalazi sedam osoba. Četiri od njih poznaju točno po jednu osobu, a preostale tri osobe poznaju točno po dvije osobe. Sva poznanstva su uzajamna.

Kolika je vjerojatnost da se dvije slučajno odabrane osobe međusobno ne poznaju?

Na kocki stranice duljine $1$ istaknuta je mreža koja se sastoji od $14$ točaka i $36$ dužina. Točke su vrhovi kocke i središta njezinih strana. Dužine su svi bridovi kocke i još po četiri dužine na svakoj strani kocke koje spajaju središte te strane s njezinim vrhovima.

Kolika je duljina najkraćeg puta po toj mreži koji prolazi kroz svih $14$ točaka?

Na kružnici je označeno $3000$ točaka. Muha koja se u početku nalazi na jednoj od točaka kreće se isključivo skokovima u smjeru kazaljke na satu za $2$ ili $3$ mjesta. Koliko joj je najmanje skokova potrebno za obilazak svih točaka i povratak na početnu točku?