Marking Scheme

ICO2022
September 2022

Problems
1. Each element of the set X = {1, 2, . . . , 6561} is colored with blue or red. Prove that there exists a
monochromatic subset A of X with size 9 such that no two subsets of A have equal sum of elements.
2. The cells of a 7 × 7 board are colored black and white as shown. We say that two black cells belong
to the same patch if it is possible to move from one of them to the other one by a sequence of steps,
where each step goes between two black cells that share a side. (Thus A and B belong to the same
patch, whereas B and C do not.) In a single move, Fiona can swap either two rows or two columns of
the board. Prove that after an arbitrary finite number of moves, the black cells will form 9 patches.

A
C
B

3. Vahid and Omid are playing a game. Initially there are three bundles of matches, consisting of 2021,
2022 and 2023 pieces. Each player in his turn chooses a bundle B and removes a positive number of
the matches of B such that the number of pieces of bundles still form an arithmetic sequence. The
player who cannot do a legal move loses. Determine which player has the winning strategy.
4. For the n-tuple A = (a1 , a2 , . . . , an ) of (not necessarily distinct) positive integers define S(A, k) as
the multiset of all sums of k consecutive elements of A (So |S(A, k)| = n − k + 1). For example if
A = (1, 3, 2, 1, 2) then S(A, 3) = {5, 6, 6}. Let A, B be two n-tuples of positive integers such that for
every 1 ≤ k ≤ n we have S(A, k) = S(B, k). Can we conclude that A,B are either equal or reflected
version of each other (i.e. (a1 , a2 , . . . , an−1 , an ) = (bn , bn−1 , . . . , b2 , b1 ))?
5. A finite number of points are marked in a square with side length n > 100. Each marked point has a
positive weight less than n2 . We√know that if the weight of a point is a, then the sum of the weights of
all points in a disk with radius a around this point is at most 6a. Prove that the sum of the weights
of all points is less than 36n2 .
6. A {−1, 0, +1} labeling of the edges of a graph G is called a ”beautiful labeling” if for each edge e, the
sum of the labels for the edges that share an endpoint with e (including e) is positive. For a graph G,
we define f (G) to be the minimum possible sum of a beautiful labeling of G. What is f (K2022,2022 ),
where K2022,2022 is a complete bipartite graph with 2022 vertices on each side?
7. All the cells of 1 × 2n table are initially white. At each step we are allowed to take a pair of consecutive
cells that have the same color and reverse their colors. (From white to black or vice versa). By
repeating this process arbitrarily many times, what is the number of different coloring patterns we can
reach? (2 coloring patterns are different if and only if there exists an index i such that the i-th cell
does not have the same color in these patterns.)
Solutions
1. Let A = {a1 , ..., ar } and B = {b1 , ..., bs } be a maximum size feasible blue and red
∑set respectively.
∑
Assume on the contrary that s, r < 9. Now each x ∈ X can be written in the form y∈Y y − z∈Z z
where Y and Z are both subsets of A or they are both subsets of B (otherwise one can increase the
size of A or B which ∑ is a contradiction).
∑ Observe that the number of ways to choose Y and Z as a
subset of A such that y∈Y y − z∈z z is positive is 3 2−1 . Therefore, 3 2−1 + 3 2−1 ≥ |X| = 6561. But
r r s

since r, s ≤ 8 then 3 2−1 + 3 2−1 < 6561 which is a contradiction (10 points).
r s

2. Note that in the initial coloring, every two rows (and likewise every two columns) have a single black
cell in common: Indeed, the first row shares the 1st cell with rows 3 and 4, the 5th cell with rows 5
and 7, and the 6th cell with rows 2 and 6 (and the claim for other pairs of rows or columns follows by
symmetry) (1 point).
Moreover, this property is clearly maintained upon performing a single move (1 point).

Consider the board after an arbitrary finite number of moves. Consider a graph G whose nodes
correspond to black cells and where two nodes are connected by an edge if the two black cells share a
side (1 point).
Clearly G has 21 nodes and by the above property it has 12 edges (six horizontal edges between pairs
of consecutive columns, and six vertical edges between pairs of consecutive rows) (1 point).
Moreover, since for every pair of consecutive columns there is fewer than two edges connecting them,
the graph G does not contain any cycles (2 points).
Therefore G has 21 − 12 = 9 connected components, each component corresponding to a single patch
(4 points).
3. The first player has the winning strategy (1 point).
We prove by induction that if the game starts with the sequence 2k, 2k + 1, 2k + 2 for non-negative k,
then the second player has the winning strategy. If k = 0 the claim trivially holds. If k ≥ 1, the first
player either turns the sequence into 2k − 1, 2k, 2k + 1 or to 2k − 2, 2k, 2k + 2. In both cases the second
player can change the sequence into 2(k − 1), 2(k − 1) + 1, 2k in which he has the winning strategy by
inductive hypothesis.
Using this lemma clearly the first player can change the sequence to 2020, 2021, 2022 in which he has
a winning strategy (9 points).
4. The answer is NO (0 points).
Let r, s ≥ 2 be positive integers and let d1 , d2 , . . . , dr and t1 , t2 , . . . , ts be distinct positive integers in
such a way that every ti is greater than D = d1 + d2 + · · · + dr . Define (rs + r + s)-tuples A, B of
positive integers as

A = (d1 , d2 , . . . , dr , t1 − D, d1 , d2 , . . . , dr , t2 − D, . . . , d1 , d2 , . . . , dr , ts − D, d1 , d2 , . . . , dr ),

B = (d1 , d2 , . . . , dr , ts − D, d1 , d2 , . . . , dr , ts−1 − D, . . . , d1 , d2 , . . . , dr , t1 − D, d1 , d2 , . . . , dr )

Page 2
 (7 points).
One can easily check that for every 1 ≤ k ≤ rs + r + s we have S(A, k) = S(B, k), and A, B are neither
equal nor reflected version of each other (3 points).
Remark. The construction comes from the length of segments created by U + V and also by U − V
for appropriate point sets U, V on a line.

5. We present a greedy algorithm to cover all the points with a set of disks. In the first step, take the
√
point with maximum weight a1 and consider a disk with radius a1 around it. Then in step i, among
all points which are yet not covered by the union of already considered disks, take the point with the
√
maximum weight ai and consider a disk with radius ai around it. We continue until all the points
are covered by at least one disk. So by the problem condition, the sum of the weights of all points is
at most 6Σai (5 points). (*)
The disks may overlap, but if we shrink them by a factor of 2 then they become disjoint, because
according to the greedy algorithm, for every i, j the distance between the two points with labels ai , aj
√ √
is larger than max{ ai , aj }. For every shrunken disk, at least a quarter is completely inside the
n × n square. So the sum of areas of these quarter disks is at most n2 which means the sum of areas
of the shrunken disks is at most 4n2 . So we have πΣai ≤ 16n2 (4 points).
This inequality together with (*) concludes the statement (1 point).
6. Answer: 2022 (1 point).
Take a complete matching and label it by +1 and label the rest by 0. This clearly forms a beautiful
labeling (1 point).
We show that f (G) ≥ 2022; Let p(v) be the sum of the labels on the edges incident to v. If p(v) ≥ 1
for every vertex v, then the sum of the labels is at least 4044 × 1/2 = 2022 (1 point).
Hence we can assume that there exists a vertex v such that p(v) ≤ 0. Now let u1 , u2 , ..., u2022 be the
neighbors of v. For every i it holds that p(ui ) + p(v) + l(vui ) ≥ 1, where l(vui ) is the label on the
∑2022 ∑2022
edge vui . Therefore i=1 (p(ui ) + p(v) + l(vui )) ≥ 2022. Thus i=1 p(ui ) + 2022p(v) + p(v) ≥ 2022,
∑2022 ∑2022
which implies i=1 p(ui ) ≥ 2022. Observe that i=1 p(ui ) is equal to the sum of all the labels, which
completes the proof (7 points).
∑n ( )2 ( )
7. Answer: i=1 ni = 2n n (1 point).
We show that we can reach a pattern P if and only if in P the number of black cells with odd index is
equal to the number of black cells with even index. Observe that any time we make a move we either
decrease the number of odd and even black cells by one or we increase both by one unit and hence we
proved one direction of the statement (4 points).
Now Assume P is a pattern in which the number of black cells with odd index is equal to the number
of black cells with even index. Let |P | denote the number of black cells of P . Clearly if |P | = 0, then
P is reachable. Assume P is reachable if P = 2k for some integer k. Now assume |P | = 2(k + 1). Let
i, j be two indices such that 1 ≤ i < j ≤ 2n, i and j have different parities, the i-th and j-th cell of P
are black and j − i is the minimum possible number. Note that clearly for each i < r < j, the r-th cell
must be white (otherwise we could rather choose r, j or i, r instead of i, j). Now let P ′ be the pattern
obtained from P by turning its i-th and j-th to white. Clearly |P ′ | = 2k and hence P ′ is reachable.
Now we show that there is a sequence of legal moves by which we can turn P ′ into P . For this purpose
one can first change the color of i, i + 1, then i + 2, i + 3, ..., and j − 1, j to black. Then we change the
color of i + 1, i + 2, i + 3, i + 4, ..., and j − 2, j − 1 to white (5 points).

Page 3