Lesson 1

Basic Problems.

1. (10 points) Does there exist a sequence of 10 numbers such that the sum of any five consecutive numbers is positive, whereas the sum of any seven consecutive numbers is negative?
   Hint:

   It is possible!
2. (10 points) Is it possible to place the numbers \(-1\), \(0\), and \(+1\) in a \(6 \times 6\)-grid so that the sums of all six rows, six columns, and the two main diagonals are pairwise distinct?
   Hint:

   One needs \(14\) different sums.
3. (10 points) In the nodes of an integer grid, five points are marked. Prove that at least one of the segments connecting these points passes through a grid node distinct from its endpoints.
   Hint:

   Consider a segment joining points \((x_{1},y_{1})\) and \((x_{2},y_{2})\). Its mid-point is \(((x_{1}+x_{2})/2, (y_{1}+y_{2})/2)\). This is a grid point if \(x_{1}\) and \(x_{2}\) have the same parity as well as \(y_{1}\) and \(y_{2}\) have the same parity.
4. (10 points) \(n\) points are marked on a circle, and some pairs of these points are connected by segments. Prove that there are two points having the same number of incident segments.

   For example, in the figure below, there are two points with two adjacent segments.

   

   Hint:

   If all the \(n\) numbers are different, then there are numbers \(0\) and \(n-1\).
5. (10 points) Five points are placed inside a unit square (a square with side length \(1\)). Prove that there exist two points that are no more than \(\frac{\sqrt{ 2 }}{2}\) apart.
   Hint:

   Divide the square into four smaller, equal-sized squares.
6. (10 points) Prove that for any \(n+1\) numbers selected from \([2n]=\{1,2,\dotsc,2n\}\), there are two co-prime numbers.
   Hint:

   Try to partition the set \([2n]\) into \(n\) “pigeonholes” such that any two numbers drawn from the same pigeonhole are co-prime.
7. (10 points) Prove that for any \(n+1\) numbers selected from \([2n]=\{1,2,\dotsc,2n\}\), there are two numbers such that one of them divides the other one.
   Hint:

   Consider classifying numbers based on their prime factorization. Specifically, try writing every integer \(x\) in the form \(x = 2^{k}\cdot m\), where \(m\) is an odd number. How many possible values can the odd part, \(m\), take?
8. (10 points) Prove that in any sequence of \(n\) integers, there exists a continuous subsequence whose sum is divisible by \(n\). (Formally: Let \(a_{1}, a_{2}, \dotsc, a_{n}\) be a sequence of integers; then there exist \(1 \le l \le r \le n\) such that \(a_{l}+a_{l+1}+\dotsb+a_{r}\) is divisible by \(n\).) For example, in the sequence \((7,2,4,9,7)\), there are two such subsequences (whose sum is divisible by five): \((2,4,9)\) and \((4,9,7)\).
   Hint:

   Consider \(n+1\) prefix sums: \[S_{0} = 0, S_{1} = a_{1}, S_{2}=a_{1}+a_{2}, \dotsb, S_{n} = a_{1} + \dotsb + a_{n}.\] What are their remainders modulo \(n\)?
9. (10 points) Prove that, for any \(x_{1}, \dotsc, x_{11}\in \mathbb{Z}\), there exist \(\alpha_{1}, \dotsc, \alpha_{11}\in \{-1, 0, 1\}\) not all being zero, such that \[2025 \text{ divides }\alpha_{1}x_{1}+\dotsb+\alpha_{11}x_{11}.\]
   Hint:

   Consider all \(2^{11}\) linear \(0/1\)-combinations of the \(x\) values.
10. (15 points) A chessmaster has \(77\) days to prepare for a tournament. She desires to play at least one game every day but not more than \(132\) games in total. Prove that there exists a sequence of consecutive days during which she plays exactly \(21\) games.
    Hint:

    Let \(g_{i}\) be the total number of games played up to and including day \(i\). Consider the sequence \(g_{1}, g_{2}, …, g_{77}\) and the sequence \(g_{1} + 21, g_{2} + 21, …, g_{77}+ 21\).
11. (15 points) What is the minimum number of colors needed to color all positive integers under a condition that \(n\) and \(2n\) have different colors as well as \(n\) and \(n+2\) have different colors (for all \(n\))?
    Hint:

    To establish a lower bound, attempt to find a small set of integers that must all have different colors from each other. For example, consider the numbers \(4\), \(6\), and \(8\).
12. (15 points) A row of \(n\) coins is laid out: heads, tails, heads, tails, and so on. In one move, it is allowed to flip any number of consecutive coins. What is the minimum number of moves required to ensure that all the coins are heads up?
    Hint:

    Consider the number of boundaries (i.e., the number of neighboring pairs of different sides) and how it changes when one flips the consecutive sequence of coins.
13. (15 points) Prove that, for any \(n, m \in \mathbb{Z}_{\ge 1}\), any sequence of distinct real numbers of length at least \(mn + 1\) contains a monotonically increasing subsequence of length \(m + 1\) or a monotonically decreasing subsequence of length \(n + 1\).
    Hint:

    For each element \(x_{k}\), where \(1 \le k \le mn + 1\), in the sequence, associate it with an ordered pair of integers \((i_{k}, d_{k})\). Here, \(i_{k}\) represents the length of the longest increasing subsequence ending at \(x_{k}\), and \(d_{k}\) represents the length of the longest decreasing subsequence ending at \(x_{k}\). What can you say about these pairs?