Search

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.

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

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?

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?

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.

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.

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.

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 su $m$ i $n$ prirodni brojevi, $m, n > 1$. U svakom polju ploče dimenzija $m \times n$ nalazi se jedan novčić. Svaki novčić ima dvije strane - pismo i glavu.

Jedan potez sastoji se od sljedećeg:

(i) Odaberemo $2 \times 2$ potkvadrat na ploči.

(ii) Preokrenemo točno tri novčića u tom potkvadratu:

• novčić u gornjem lijevom polju
• novčić u donjem desnom polju
• jedan od novčića u gornjem desnom i donjem lijevom polju (po izboru).

Ako na početku svi novčići pokazuju pismo, odredi sve parove $(m,n)$ za koje se konačnim nizom poteza može postići da svi novčići pokazuju glavu.

Na nekim poljima ploče dimenzija $300 \times 300$ postavljene su kule, figure koje kontroliraju sva polja u svom stupcu i retku. Kule su raspoređene tako da svako polje ploče kontrolira barem jedna kula, a svaka kula kontrolira najviše jedno polje na kojem je neka druga kula. Odredi najmanji prirodni broj $k$ takav da se u svakom kvadratu dimenzija $k \times k$ sigurno nalazi barem jedna kula.

Consider decompositions of an $8 \times 8$ chessboard into $p$ non-overlapping rectangles subject to the following conditions:

(i) Each rectangle has as many white squares as black squares.

(ii) If $a_i$ is the number of white squares in the $i$-th rectangle, then $a_1 < a_2 < \cdots < a_p$. Find the maximum value of $p$ for which such a decomposition is possible. For this value of $p$, determine all possible sequences $a_1, a_2, \ldots, a_p$.

On an infinite chessboard, a game is played as follows. At the start, $n^2$ pieces are arranged on the chessboard in an $n$ by $n$ block of adjoining squares, one piece in each square. A move in the game is a jump in a horizontal or vertical direction over an adjacent occupied square to an unoccupied square immediately beyond. The piece which has been jumped over is removed.

Find those values of $n$ for which the game can end with only one piece remaining on the board.

We are given a positive integer $r$ and a rectangular board $ABCD$ with dimensions $|AB| = 20$, $|BC| = 12$. The rectangle is divided into a grid of $20 \times 12$ unit squares. The following moves are permitted on the board: one can move from one square to another only if the distance between the centers of the two squares is $\sqrt{r}$. The task is to find a sequence of moves leading from the square with $A$ as a vertex to the square with $B$ as a vertex.

(a) Show that the task cannot be done if $r$ is divisible by 2 or 3.

(b) Prove that the task is possible when $r = 73$.

(c) Can the task be done when $r = 97$?

Consider an $n \times n$ square board, where $n$ is a fixed even positive integer. The board is divided into $n^2$ unit squares. We say that two different squares on the board are adjacent if they have a common side.

$N$ unit squares on the board are marked in such a way that every square (marked or unmarked) on the board is adjacent to at least one marked square.

Determine the smallest possible value of $N$.

Define a "hook" to be a figure made up of six unit squares as shown below in the picture, or any of the figures obtained by applying rotations and reflections to this figure.

Determine all $m \times n$ rectangles that can be covered without gaps and without overlaps with hooks such that

• the rectangle is covered without gaps and without overlaps

• no part of a hook covers area outside the rectangle.

Let $n \geq 2$ be an integer. Consider an $n \times n$ chessboard consisting of $n^2$ unit squares. A configuration of $n$ rooks on this board is peaceful if every row and every column contains exactly one rook. Find the greatest positive integer $k$ such that, for each peaceful configuration of $n$ rooks, there is a $k \times k$ square which does not contain a rook on any of its $k^2$ unit squares.

A site is any point $(x, y)$ in the plane such that $x$ and $y$ are both positive integers less than or equal to 20.

Initially, each of the 400 sites is unoccupied. Amy and Ben take turns placing stones with Amy going first. On her turn, Amy places a new red stone on an unoccupied site such that the distance between any two sites occupied by red stones is not equal to $\sqrt{5}$. On his turn, Ben places a new blue stone on any unoccupied site. (A site occupied by a blue stone is allowed to be at any distance from any other occupied site.) They stop as soon as a player cannot place a stone.

Find the greatest $K$ such that Amy can ensure that she places at least $K$ red stones, no matter how Ben places his blue stones.

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.

Turbo the snail plays a game on a board with 2024 rows and 2023 columns. There are hidden monsters in 2022 of the cells. Initially, Turbo does not know where any of the monsters are, but he knows that there is exactly one monster in each row except the first row and the last row, and that each column contains at most one monster.

Turbo makes a series of attempts to go from the first row to the last row. On each attempt, he chooses to start on any cell in the first row, then repeatedly moves to an adjacent cell sharing a common side. (He is allowed to return to a previously visited cell.) If he reaches a cell with a monster, his attempt ends and he is transported back to the first row to start a new attempt. The monsters do not move, and Turbo remembers whether or not each cell he has visited contains a monster. If he reaches any cell in the last row, his attempt ends and the game is over.

Determine the minimum value of $n$ for which Turbo has a strategy that guarantees reaching the last row on the $n^{\text{th}}$ attempt or earlier, regardless of the locations of the monsters.

Consider a $2025 \times 2025$ grid of unit squares. Matilda wishes to place on the grid some rectangular tiles, possibly of different sizes, such that each side of every tile lies on a grid line and every unit square is covered by at most one tile.

Determine the minimum number of tiles Matilda needs to place so that each row and each column of the grid has exactly one unit square that is not covered by any tile.

We colour every square of the $2009 \times 2009$ board with one of $n$ colours (we do not have to use every colour). A colour is called connected if either there is only one square of that colour or any two squares of the colour can be reached from one another by a sequence of moves of a chess queen without intermediate stops at squares having another colour (a chess queen moves horizontally, vertically or diagonally). Find the maximum $n$, such that for every colouring of the board at least one colour present at the board is connected.

Let $n$ be a positive integer. On a board consisting of $4n \times 4n$ squares, exactly $4n$ tokens are placed so that each row and each column contains one token. In a step, a token is moved horizontally or vertically to a neighbouring square. Several tokens may occupy the same square at the same time. The tokens are to be moved to occupy all the squares of one of the two diagonals.

Determine the smallest number $k(n)$ such that for any initial situation, we can do it in at most $k(n)$ steps.

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$

A tract of land in the shape of an $8 \times 8$ square, whose sides are oriented north-south and east-west, consists of $64$ smaller $1 \times 1$ square plots. There can be at most one house on each of the individual plots. A house can only occupy a single $1 \times 1$ square plot.

A house is said to be blocked from sunlight if there are three houses on the plots immediately to its east, west and south.

What is the maximum number of houses that can simultaneously exist, such that none of them is blocked from sunlight?

Remark: By definition, houses on the east, west and south borders are never blocked from sunlight.

The two figures depicted below consisting of $6$ and $10$ unit squares, respectively, are called staircases.

Consider a $2018 \times 2018$ board consisting of $2018^2$ cells, each being a unit square. Two arbitrary cells were removed from the same row of the board. Prove that the rest of the board cannot be cut (along the cell borders) into staircases (possibly rotated).

Let $m$ and $n$ be positive integers. Some squares of an $m \times n$ board are coloured red. A sequence $a_1, a_2, \ldots, a_{2r}$ of $2r \geqslant 4$ pairwise distinct red squares is called a bishop circuit if for every $k \in \{1, \ldots, 2r\}$, the squares $a_k$ and $a_{k+1}$ lie on a diagonal, but the squares $a_k$ and $a_{k+2}$ do not lie on a diagonal (here $a_{2r+1} = a_1$ and $a_{2r+2} = a_2$).

In terms of $m$ and $n$, determine the maximum possible number of red squares on an $m \times n$ board without a bishop circuit.

(Remark. Two squares lie on a diagonal if the line passing through their centres intersects the sides of the board at an angle of $45°$.)

Let $n$ be a positive integer. We are given a $2n \times 2n$ table. Each cell is coloured with one of $2n^2$ colours such that each colour is used exactly twice. Jana stands in one of the cells. There is a chocolate bar lying in one of the other cells. Jana wishes to reach the cell with the chocolate bar. At each step, she can only move in one of the following two ways. Either she walks to an adjacent cell or she teleports to the other cell with the same colour as her current cell. (Jana can move to an adjacent cell of the same colour by either walking or teleporting.) Determine whether Jana can fulfill her wish, regardless of the initial configuration, if she has to alternate between the two ways of moving and has to start with a teleportation.

Remark. Two cells are adjacent if they share a common edge.

Find the smallest integer $b$ with the following property: For each way of colouring exactly $b$ squares of an $8 \times 8$ chessboard green, one can place 7 bishops on 7 green squares so that no two bishops attack each other.

Remark. Two bishops attack each other if they are on the same diagonal.

On an infinite square grid, on which some unit squares are coloured red, a ruby rook is a piece which, in one move, can travel any number of squares in one direction parallel to one of the grid lines (either vertically or horizontally), while remaining on red squares at all times throughout the move.

Starting with an uncoloured infinite square grid, Alice performs the following procedure: First, she colours at most 2025 of the unit squares red. Afterwards, she places some ruby rooks on distinct red unit squares, such that the following two rules are satisfied:

• No ruby rook can reach another ruby rook in one move.
• Every ruby rook can reach every other ruby rook in two moves.

Find the maximum possible number of ruby rooks that Alice can place during this procedure.

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?

a) Dokažite da se ploča dimenzija $4 \times 4$ može obojiti u dvije boje tako da za svaki izbor dvaju redaka i dvaju stupaca vrijedi da četiri polja u presjecima tih redaka i stupaca nisu sva obojana istom bojom.

b) Dokažite da gore navedeno svojstvo ne vrijedi za ploču dimenzija $5 \times 5$.

Dana je dvadeset i jedna točka kao na slici.

Na početku je svakoj točki pridružen broj nula.

U svakom potezu odabire se pravac koji sadrži neku od nacrtanih dužina i u svim točkama kroz koje taj pravac prolazi, pridruženi brojevi se povećavaju za $1$.

Kažemo da je prirodni broj $n$ dohvatljiv ako se na opisani način može postići da je nakon određenog broja poteza svim točkama pridružen isti broj $n$.

a) Dokaži da je broj $2010$ dohvatljiv.

b) Dokaži da broj $2011$ nije dohvatljiv.

Polja ploče dimenzija $N \times N$ obojana su u crno i bijelo tako da su polja koja imaju zajedničku stranicu različite boje i tako da je barem jedno polje u kutu ploče crne boje. U pojedinom koraku odabire se kvadrat dimenzija $2 \times 2$ i sva četiri polja unutar tog kvadrata mijenjaju boju tako da bijela polja postaju crna, crna postaju siva, a siva postaju bijela.

Odredi sve prirodne brojeve $N > 1$ za koje je konačnim nizom opisanih koraka moguće postići da sva polja koja su na početku bila crna budu bijela i da sva polja koja su na početku bila bijela budu crna.

Ana je prekrila ploču dimenzija $2020 \times 2020$ domino pločicama koje se međusobno ne preklapaju, a svaka od njih prekriva točno dva polja ploče. Branka želi obojiti te pločice tako da za svaku vrijedi: među njoj susjednim pločicama najviše su dvije u boji promatrane. Dvije pločice su susjedne ako prekrivaju polja koja imaju zajedničku stranicu.

Koliko je najmanje boja potrebno da bi Branka sigurno mogla obojiti pločice na takav način, neovisno o načinu na koji ih je Ana rasporedila?

Iz ploče dimenzija $2025 \times 2025$ uklonjen je kvadrat dimenzija $7 \times 7$, a preostali dio ploče prekriva se pločicama dimenzija $1 \times 4$ (tako da svaka pločica prekriva točno četiri polja).

(a) Ako uklonimo središnji $7 \times 7$ kvadrat, dokaži da je preostali dio ploče moguće pokriti pločicama dimenzija $1 \times 4$.

(b) Ako uklonimo $7 \times 7$ kvadrat koji sadrži jedan ugao ploče, dokaži da preostali dio ploče nije moguće pokriti pločicama dimenzija $1 \times 4$.

Na koliko načina možemo obojati polja ploče $2 \times 2016$ u dvije boje tako da ne postoje tri polja iste boje koja se mogu istovremeno pokriti pločicom oblika kao na slici? Pločicu je dozvoljeno rotirati.

Na ploču dimenzija $4 \times 4$ treba rasporediti određeni broj žetona tako da se na nekim poljima nalazi po jedan žeton, a neka su polja prazna. Za raspored žetona kažemo da je siguran ako se svaki žeton nalazi na polju kojemu su sva susjedna polja prazna (dva polja smatraju se susjednima ako imaju zajedničku stranicu). Za koji najmanji prirodan broj $k$ postoji siguran raspored $k$ žetona takav da se na ploču ne može dodati nijedan žeton, a da raspored i dalje bude siguran?

Može li se ploča dimenzija $2027 \times 2027$ prekriti koristeći dvije vrste pločica:

• pločice dimenzija $1 \times 2$ koje prekrivaju po dva susjedna polja u istom retku i

• pločice dimenzija $3 \times 1$ koje prekrivaju po tri uzastopna polja u istom stupcu?

Pločice se ne smiju preklapati niti prelaziti preko ruba dane ploče.

U svako polje tablice $m \times n$ ($m, n \in \mathbb{N}$) upisano je slovo $A$ ili $B$. Pritom nikoja dva susjedna polja (sa zajedničkom stranicom) ne sadrže isto slovo. U jednom koraku biraju se dva susjedna polja, i oba slova na tim poljima zamijene se novim slovima po sljedećem pravilu:

• umjesto slova $A$ upisuje se slovo $B$,
• umjesto slova $B$ upisuje se slovo $C$,
• umjesto slova $C$ upisuje se slovo $A$.

Za koje $m$ i $n$ nakon konačno mnogo koraka možemo postići da u svim poljima u kojima je na početku bilo napisano slovo $A$ sada piše slovo $B$, a u svim poljima u kojima je na početku bilo napisano slovo $B$ sada piše slovo $A$?

Na početku je u svaki od kvadrata raspoređenih kao na slici upisana nula.

U svakom potezu odabire se jedan od kvadrata te se istovremeno brojevi koji se nalaze u tom kvadratu i u svim njemu susjednim kvadratima uvećavaju za jedan.

Dokaži da je nakon određenog broja poteza:

a) moguće postići da u svakom kvadratu piše broj $2010$;

b) nemoguće postići da u svakom kvadratu piše broj $2011$.

Može li skakač običi ploču dimenzija $4 \times 2012$ i vratiti se na polazno polje tako da pritom stane na svako polje točno jednom?

Skakač je figura koja se kreće kao u šahu: s polja označenog kružićem može se pomaknuti na jedno od osam polja označenih križićima (ako je to polje na ploči).

Dana je tablica $6 \times 6$.

a) Ako je označeno bilo kojih $9$ polja tablice, dokaži da je moguće odabrati tri retka i tri stupca koji sadrže sva označena polja.

b) Označi $10$ polja tablice tako da koja god tri retka i tri stupca odaberemo, uvijek postoji bar jedno označeno polje koje nije u odabranim stupcima niti recima.

Dana je ploča s 2016 redaka i 2017 stupaca. Je li moguće ukloniti dva polja u zadnjem stupcu te ploče tako da dobivenu ploču možemo prekriti bez preklapanja pločicama oblika kao na slici? Pločice je dozvoljeno rotirati.

Dana je kvadratna ploča s $n \times n$ polja, gdje je $n$ neparan prirodni broj. Svaki od $2n(n+1)$ jediničnih bridova koji omeđuju polja te ploče je ili crvene ili plave boje. Poznato je da je najviše $n^2$ bridova crvene boje.

Dokaži da postoji polje te ploče čija su barem tri brida plave boje.

Ana je prekrila ploču dimenzija $2020 \times 2020$ domino pločicama koje se međusobno ne preklapaju, a svaka od njih prekriva točno dva polja ploče. Branka želi obojiti te pločice tako da za svaku vrijedi: među njoj susjednim pločicama najviše je jedna u boji promatrane. Dvije pločice su susjedne ako prekrivaju polja koja imaju zajedničku stranicu.

Koliko je najmanje boja potrebno da bi Branka sigurno mogla obojiti pločice na takav način, neovisno o načinu na koji ih je Ana rasporedila?

U svako polje pravokutne ploče s 3 stupca i 14 redaka upisan je simbol $X$ ili $O$. Za ploču kažemo da je balansirana ako su zadovoljeni sljedeći uvjeti:

• svaki $3 \times 3$ kvadrat sadržava najviše 5 simbola $X$ i najviše 5 simbola $O$
• u svakom $3 \times 3$ kvadrati nijedna dijagonala ni redak ni stupac ne sadržavaju tri ista simbola.

Za balansiranu ploču $P$, centar od $P$ je ploča s 3 stupca i 12 redaka dobivena uklanjanjem prvoga i posljednjega retka iz $P$.

Među svim balansiranim pločama koliko postoji različitih centara?

Na ploči dimenzija $100 \times 100$ nalaze se dvije figure – u gornjem lijevom polju je kralj, a u gornjem desnom skakač. Figure se naizmjenično pomiču, a kralj kreće prvi. Obje figure se kreću kao u šahu: skakač se s polja označenog kružićem može pomaknuti na jedno od osam polja označenih križićima (ako je to polje na ploči), dok se kralj u svom potezu pomiče na jedno od (najviše) osam susjednih polja. Može li kralj sigurno doći do donjeg desnog polja ploče, a da ga skakač pritom ne ulovi?