2021 Iranian Combinatorics Olympiad

Part of Iranian Combinatorics Olympiad

Subcontests

(7)

1

2021 ICO Advanced P7

2021

1400

of them are \emph{saboteurs}. Sherlock wants to find one saboteur. There are some missions that each needs exactly

3

people to be done. A mission fails if at least one of the three participants in that mission is a saboteur! In each round, Sherlock chooses

3

people, sends them to a mission and sees whether it fails or not. What is the minimum number of rounds he needs to accomplish his goal?

1

2021 ICO Advanced P6

\mathcal{P}

be a convex polygon and

<span class='latex-bold'>T</span>

be a triangle with vertices among the vertices of

\mathcal{P}

<span class='latex-bold'>T</span>

\mathcal{P}

, we end up with

0, 1, 2,

3

smaller polygons (possibly with shared vertices) which we call the effect of

<span class='latex-bold'>T</span>

. A triangulation of

P

is a way of dissecting it into some triangles using some non-intersecting diagonals. We call a triangulation of

\mathcal{P}

\underline{\text{beautiful}}

, if for each of its triangles, the effect of this triangle contains exactly one polygon with an odd number of vertices. Prove that a triangulation of

\mathcal{P}

is beautiful if and only if we can remove some of its diagonals and end up with all regions as quadrilaterals.

1

2021 ICO Advanced P5

By a \emph{tile} we mean a polyomino (i.e. a finite edge-connected set of cells in the infinite grid). There are many ways to place a tile in the infinite table (rotation is allowed but we cannot flip the tile). We call a tile

<span class='latex-bold'>T</span>

special if we can place a permutation of the positive integers on all cells of the infinite table in such a way that each number would be maximum between all the numbers that tile covers in at most one placement of the tile.
1. Prove that each square is a special tile. 2. Prove that each non-square rectangle is not a special tile. 3. Prove that tile

<span class='latex-bold'>T</span>

is special if and only if it looks the same after

90^\circ

1

2021 ICO Advanced P4

\underline{\text{path number}}

of a graph is the minimum number of paths we need to partition the vertices of a graph. Given a connected graph with the independence number

k > 1

, what is the maximum possible value for the path number in this graph? Find the answer in terms of

k

.
The independence number of a graph

<span class='latex-bold'>G</span>

is the maximum possible number

k

, such that there exist

k

pairwise non-adjacent vertices in

<span class='latex-bold'>G</span>

1

2021 ICO Advanced P3

There is an ant on every vertex of a unit cube. At the time zero, ants start to move across the edges with the velocity of one unit per minute. If an ant reaches a vertex, it alternatively turns right and left (for the first time it will turn in a random direction). If two or more ants meet anywhere on the cube, they die! We know an ant survives after three minutes. Prove that there exists an ant that never dies!

1

2021 ICO Advanced P2

We assume a truck as a

1 \times (k + 1)

tile. Our parking is a

(2k + 1) \times (2k + 1)

table and there are

t

trucks parked in it. Some trucks are parked horizontally and some trucks are parked vertically in the parking. The vertical trucks can only move vertically (in their column) and the horizontal trucks can only move horizontally (in their row). Another truck is willing to enter the parking lot (it can only enter from somewhere on the boundary).
For

3k + 1 < t < 4k

, prove that we can move other trucks forward or backward in such a way that the new truck would be able to enter the lot.
Prove that the statement is not necessarily true for

t = 3k + 1

1

2021 ICO Advanced P1

In the lake, there are

23

stones arranged along a circle. There are

22

1, 2, \cdots, 22

(each number appears once). Initially, each frog randomly sits on a stone (several frogs might sit on the same stone). Every minute, all frogs jump at the same time as follows: the frog number

i

i

stones forward in the clockwise direction. (In particular, the frog number

22

1

stone in the counter-clockwise direction.) Prove that at some point, at least

6

stones will be empty.