Search

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.

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.

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?

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.

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.

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.

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

Dani su prirodan broj $m$ i prost broj $p$ takvi da je $p > m$. Dokaži da broj prirodnih brojeva $n$ za koje je $$m^2 + n^2 + p^2 - 2mn - 2mp - 2np$$ kvadrat nekog prirodnog broja ne ovisi o broju $p$.

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?

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$ prirodan broj. Na nogometnom turniru sudjeluje $2n + 1$ ekipa, a svake dvije ekipe međusobno igraju po jednu utakmicu. Sve se utakmice igraju na istom terenu, pa nije moguće da se dvije utakmice igraju istovremeno. Nikakvih drugih pravila o redoslijedu odigravanja utakmica nema.

Kažemo da je utakmica između dviju ekipa ravnopravna ako su obje ekipe do tada odigrale jednak broj utakmica. Koliko najviše ravnopravnih utakmica može biti odigrano na tom turniru?

In a mathematical contest, three problems, $A, B, C$ were posed. Among the participants there were 25 students who solved at least one problem each. Of all the contestants who did not solve problem $A$, the number who solved $B$ was twice the number who solved $C$. The number of students who solved only problem $A$ was one more than the number of students who solved $A$ and at least one other problem. Of all students who solved just one problem, half did not solve problem $A$. How many students solved only problem $B$?

Given $n > 4$ points in the plane such that no three are collinear. Prove that there are at least $\binom{n-3}{2}$ convex quadrilaterals whose vertices are four of the given points.

Find the set of all positive integers $n$ with the property that the set $\{n, n + 1, n + 2, n + 3, n + 4, n + 5\}$ can be partitioned into two sets such that the product of the numbers in one set equals the product of the numbers in the other set.

Prove that from a set of ten distinct two-digit numbers (in the decimal system), it is possible to select two disjoint subsets whose members have the same sum.

An international society has its members from six different countries. The list of members contains 1978 names, numbered $1, 2, \ldots, 1978$. Prove that there is at least one member whose number is the sum of the numbers of two members from his own country, or twice as large as the number of one member from his own country.

Let $A$ and $E$ be opposite vertices of a regular octagon. A frog starts jumping at vertex $A$. From any vertex of the octagon except $E,$ it may jump to either of the two adjacent vertices. When it reaches vertex $E,$ the frog stops and stays there. Let $a_n$ be the number of distinct paths of exactly $n$ jumps ending at $E.$ Prove that $a_{2n-1}=0,$

$$a_{2n}=\frac{1}{\sqrt{2}}(x^{n-1}-y^{n-1}),\quad n=1,2,3,\cdots,$$

where $x=2+\sqrt{2}$ and $y=2-\sqrt{2}.$

Note. A path of $n$ jumps is a sequence of vertices $(P_0,\ldots,P_n)$ such that

(i) $P_0=A, P_n=E;$

(ii) for every $i, 0\leq i\leq n-1, P_i$ is distinct from $E;$

(iii) for every $i, 0\leq i\leq n-1, P_i$ and $P_{i+1}$ are adjacent.

Let $1 \leq r \leq n$ and consider all subsets of $r$ elements of the set $\{1, 2, \ldots, n\}$. Each of these subsets has a smallest member. Let $F(n, r)$ denote the arithmetic mean of these smallest numbers; prove that $$F(n, r) = \frac{n + 1}{r + 1}.$$

Is it possible to choose 1983 distinct positive integers, all less than or equal to $10^5$, no three of which are consecutive terms of an arithmetic progression? Justify your answer.

Let $p_n(k)$ be the number of permutations of the set $\{1, \ldots, n\}$, $n \geq 1$, which have exactly $k$ fixed points. Prove that

$$\sum_{k=0}^{n} k \cdot p_n(k) = n!.$$

(Remark: A permutation $f$ of a set $S$ is a one-to-one mapping of $S$ onto itself. An element $i$ in $S$ is called a fixed point of the permutation $f$ if $f(i) = i$.)

A function $f$ is defined on the positive integers by

$$\begin{aligned} f(1) &= 1, \quad f(3) = 3, \\ f(2n) &= f(n), \\ f(4n + 1) &= 2f(2n + 1) - f(n), \\ f(4n + 3) &= 3f(2n + 1) - 2f(n), \end{aligned}$$

for all positive integers $n$.

Determine the number of positive integers $n$, less than or equal to 1988, for which $f(n) = n$.

A permutation $(x_1, x_2, \ldots, x_m)$ of the set $\{1, 2, \ldots, 2n\}$, where $n$ is a positive integer, is said to have property $P$ if $|x_i - x_{i+1}| = n$ for at least one $i$ in $\{1, 2, \ldots, 2n-1\}$. Show that, for each $n$, there are more permutations with property $P$ than without.

Let $S = \{1, 2, 3, \ldots, 280\}$. Find the smallest integer $n$ such that each $n$-element subset of $S$ contains five numbers which are pairwise relatively prime.

Consider nine points in space, no four of which are coplanar. Each pair of points is joined by an edge (that is, a line segment) and each edge is either colored blue or red or left uncolored. Find the smallest value of $n$ such that whenever exactly $n$ edges are colored, the set of colored edges necessarily contains a triangle all of whose edges have the same color.

For any positive integer $k$, let $f(k)$ be the number of elements in the set $\{k + 1, k + 2, \ldots, 2k\}$ whose base 2 representation has precisely three 1s.

• (a) Prove that, for each positive integer $m$, there exists at least one positive integer $k$ such that $f(k) = m$.
• (b) Determine all positive integers $m$ for which there exists exactly one $k$ with $f(k) = m$.

Let $p$ be an odd prime number. How many $p$-element subsets $A$ of $\{1, 2, \ldots, 2p\}$ are there, the sum of whose elements is divisible by $p$?

For each positive integer $n$, let $f(n)$ denote the number of ways of representing $n$ as a sum of powers of 2 with nonnegative integer exponents. Representations which differ only in the ordering of their summands are considered to be the same. For instance, $f(4) = 4$, because the number 4 can be represented in the following four ways:

$$4; 2 + 2; 2 + 1 + 1; 1 + 1 + 1 + 1.$$

Prove that, for any integer $n \geq 3$,

$$2^{n^2/4} < f(2^n) < 2^{n^2/2}.$$

100 cards are numbered 1 to 100 (each card different) and placed in 3 boxes (at least one card in each box). How many ways can this be done so that if two boxes are selected and a card is taken from each, then the knowledge of their sum alone is always sufficient to identify the third box?

Twenty-one girls and twenty-one boys took part in a mathematical contest.

• Each contestant solved at most six problems.
• For each girl and each boy, at least one problem was solved by both of them.

Prove that there was a problem that was solved by at least three girls and at least three boys.

$S$ is the set of all $(h,k)$ with $h,k$ non-negative integers such that $h+k<n$. Each element of $S$ is colored red or blue, so that if $(h,k)$ is red and $h'\leq h,k'\leq k$, then $(h',k')$ is also red. A type 1 subset of $S$ has $n$ blue elements with different first member and a type 2 subset of $S$ has $n$ blue elements with different second member. Show that there are the same number of type 1 and type 2 subsets.

In a mathematical competition, in which 6 problems were posed to the participants, every two of these problems were solved by more than $\frac{2}{5}$ of the contestants. Moreover, no contestant solved all the 6 problems. Show that there are at least 2 contestants who solved exactly 5 problems each.

Let $P$ be a regular 2006-gon. A diagonal of $P$ is called good if its endpoints divide the boundary of $P$ into two parts, each composed of an odd number of sides of $P$. The sides of $P$ are also called good.

Suppose $P$ has been dissected into triangles by 2003 diagonals, no two of which have a common point in the interior of $P$. Find the maximum number of isosceles triangles having two good sides that could appear in such a configuration.

Let $n$ and $k$ be positive integers with $k \geq n$ and $k - n$ an even number. Let $2n$ lamps labelled 1, 2, ..., $2n$ be given, each of which can be either on or off. Initially all the lamps are off. We consider sequences of steps: at each step one of the lamps is switched (from on to off or from off to on).

Let $N$ be the number of such sequences consisting of $k$ steps and resulting in the state where lamps 1 through $n$ are all on, and lamps $n + 1$ through $2n$ are all off.

Let $M$ be the number of such sequences consisting of $k$ steps, resulting in the state where lamps 1 through $n$ are all on, and lamps $n + 1$ through $2n$ are all off, but where none of the lamps $n + 1$ through $2n$ is ever switched on.

Determine the ratio $N/M$.

Let $n > 0$ be an integer. We are given a balance and $n$ weights of weight $2^0, 2^1, \ldots, 2^{n-1}$. We are to place each of the $n$ weights on the balance, one after another, in such a way that the right pan is never heavier than the left pan. At each step we choose one of the weights that has not yet been placed on the balance, and place it on either the left pan or the right pan, until all of the weights have been placed.

Determine the number of ways in which this can be done.

Let $n \geq 3$ be an integer, and consider a circle with $n + 1$ equally spaced points marked on it. Consider all labellings of these points with the numbers $0, 1, \ldots, n$ such that each label is used exactly once; two such labellings are considered to be the same if one can be obtained from the other by a rotation of the circle. A labelling is called beautiful if, for any four labels $a < b < c < d$ with $a + d = b + c$, the chord joining the points labelled $a$ and $d$ does not intersect the chord joining the points labelled $b$ and $c$.

Let $M$ be the number of beautiful labellings, and let $N$ be the number of ordered pairs $(x,y)$ of positive integers such that $x + y \leq n$ and $\gcd(x,y) = 1$. Prove that

$$M = N + 1.$$

Let $n$ be a positive integer. A Nordic square is an $n \times n$ board containing all the integers from 1 to $n^2$ so that each cell contains exactly one number. Two different cells are considered adjacent if they share a common side. Every cell that is adjacent only to cells containing larger numbers is called a valley. An uphill path is a sequence of one or more cells such that:

(i) the first cell in the sequence is a valley,

(ii) each subsequent cell in the sequence is adjacent to the previous cell, and

(iii) the numbers written in the cells in the sequence are in increasing order.

Find, as a function of $n$, the smallest possible total number of uphill paths in a Nordic square.

There are $n\geq 2$ houses on the northern side of a street. Going from the west to the east, the houses are numbered from $1$ to $n$. The number of each house is shown on a plate. One day the inhabitants of the street make fun of the postman by shuffling their number plates in the following way: for each pair of neighbouring houses, the current number plates are swapped exactly once during the day.

How many different sequences of number plates are possible at the end of the day?

The numbers from $1$ to $2013^{2}$ are written row by row into a table consisting of $2013 \times 2013$ cells. Afterwards, all columns and all rows containing at least one of the perfect squares $1,4,9,\ldots,2013^{2}$ are simultaneously deleted.

How many cells remain?

Let $N$ be a positive integer. In each of the $N^2$ unit squares of an $N \times N$ board, one of the two diagonals is drawn. The drawn diagonals divide the $N \times N$ board into $K$ regions. For each $N$, determine the smallest and the largest possible values of $K$.

Example with $N = 3$, $K = 7$

Let $n \geq 2$ be an integer. Determine the number of positive integers $m$ such that $m \leq n$ and $m^2 + 1$ is divisible by $n$.

There are $n$ boys and $n$ girls in a school class, where $n$ is a positive integer. The heights of all the children in this class are distinct. Every girl determines the number of boys that are taller than her, subtracts the number of girls that are taller than her, and writes the result on a piece of paper. Every boy determines the number of girls that are shorter than him, subtracts the number of boys that are shorter than him, and writes the result on a piece of paper. Prove that the numbers written down by the girls are the same as the numbers written down by the boys (up to a permutation).

Let $n \geqslant 3$ be an integer. Zagi the squirrel sits at a vertex of a regular $n$-gon. Zagi plans to make a journey of $n - 1$ jumps such that in the $i$-th jump, it jumps by $i$ edges clockwise, for $i \in \{1, \ldots, n - 1\}$. Prove that if after $\lceil \frac{n}{2} \rceil$ jumps Zagi has visited $\lceil \frac{n}{2} \rceil + 1$ distinct vertices, then after $n - 1$ jumps Zagi will have visited all of the vertices.

(Remark. For a real number $x$, we denote by $\lceil x \rceil$ the smallest integer larger or equal to $x$.)

Let $n$ be a positive integer. There are $n$ purple and $n$ white cows queuing in a line in some order. Tim wishes to sort the cows by colour, such that all purple cows are at the front of the line. At each step, he is only allowed to swap two adjacent groups of equally many consecutive cows. What is the minimal number of steps Tim needs to be able to fulfill his wish, regardless of the initial alignment of the cows?

Example. For instance, Tim can perform the following three swaps: $$W\underline{PW}\overline{PP}W \longrightarrow \underline{W}\overline{P}PPWW \longrightarrow P\underline{WP}\overline{PW}W \longrightarrow PPWWPW.$$

Find all integers $n \geq 3$ for which it is possible to draw $n$ chords of one circle such that their $2n$ endpoints are pairwise distinct and each chord intersects precisely $k$ other chords for:

(a) $k = n - 2$,

(b) $k = n - 3$.

Remark. A chord of a circle is a line segment whose both endpoints lie on the circle.

A snake in an $n \times n$ grid is a path composed of straight line segments between centres of adjacent cells, going through the centres of all the $n^2$ grid cells, which visits each cell exactly once. Here two grid cells are considered to be adjacent if they share an edge. Note that all pieces of the snake path are parallel to grid lines. The figure shows an example of a snake in a $4 \times 4$ grid. This snake makes nine $90^\circ$ turns, marked by small black squares.

Let us now consider a snake through the 2025 cells of a $45 \times 45$ grid. What is the maximum possible number of $90^\circ$ turns that such a snake can make?

Na beskonačnom bijelom papiru podijeljenom na jednake kvadratiće neki od njih su obojeni crvenom bojom. U svakom $2 \times 3$ pravokutniku točno dva kvadratića su crvena. Promatrajte bilo koji $9 \times 11$ pravokutnik. Koliko u njemu ima crvenih kvadratića?

Neka je $m \geq 2$ prirodan broj. Koliko rješenja u skupu prirodnih brojeva ima jednadžba $$\left\lfloor \frac {x}{m} \right\rfloor = \left\lfloor \frac {x}{m - 1} \right\rfloor ?$$ ($\lfloor x \rfloor$ je oznaka za najveći cijeli broj koji nije veći od $x$.)

"Kolo sreće" podijeljeno je na $30$ odjeljaka u koje su upisani brojevi $50$, $100$, $150$, ..., $1500$ (u nekom redoslijedu). Dokažite da postoje tri uzastopna odjeljka u kojima je zbroj upisanih brojeva veći ili jednak $2350$.