Lesson 1

Basic Problems.

1. (10 points) Prove that, for any \(n \in \mathbb{Z}_{\ge 1}\), \[1\cdot(n-1)+2\cdot(n-2)+…+(n-1)\cdot1 = \frac{(n-1)n(n+1)}{6}\ .\]
2. (10 points) Prove that, for any \(n \in \mathbb{Z}_{\ge 2}\), \[\frac{1}{n+1}+ \frac{1}{n+2}+ … + \frac{1}{2n}> \frac{13}{24}.\]
3. (10 points) In a round-robin tournament with no draws, each of the \(n\) teams played against every other team. A list of teams \(p_{1}, p_{2}, …, p_{k}\) is called a cycle in the tournament if \(p_{1}\) beat \(p_{2}\), \(p_{2}\) beat \(p_{3}\), …, and \(p_{k}\) beat \(p_{1}\). Prove that if there is a cycle in the tournament, then there is also a cycle involving three teams.
4. (10 points) Prove that, for any \(n \in \mathbb{Z}_{\ge 1}\), \(5^{n} - 1\) is divisible by \(4\).
5. (10 points) Prove that, for any \(n \in \mathbb{Z}_{\ge 1}\), \[1 + \frac{1}{4}+ \frac{1}{9}+ \dotsb + \frac{1}{n^2}\le 2 - \frac{1}{n}.\]
6. (15 points) A celebrity is someone who is known by everyone but does not know anyone. Prove that at a party with \(n \in \mathbb{Z}_{\ge 2}\) persons you can check whether there is a celebrity by asking at most \(3(n-1)\) questions of the form “Excuse me, do you know the person over there?”
7. (15 points) Prove that, for any \(n \in \mathbb{Z}_{\ge 6}\), a square can be divided into \(n\) squares.
   Hint:

   The base case is \(n=6,7,8\).
8. (15 points) Prove that for any \(n\ge 3\) points on a plane, no three of which lie on the same line, it is possible to construct a simple closed polygonal path that has these points as its vertices.
   Hint:

   Proving the step \(n-1 \to n\) is a pain. Instead, you may want to use the method of the minimum counterexample: consider a way of connecting the points into a cycle of minimal total length and prove that it has no crossings.
9. (15 points) Prove that an integer consisting of \(243\) ones is divisible by \(243\).
   Hint:

   \(243\) is a power of \(3\). Strengthen the statement.
10. (15 points) A maze is a \(10 \times 10\) grid, where certain pairs of adjacent nodes are connected by a segment called a “wall” such that one can move from a cell to its adjacent cell (by its side) without crossing the walls, ensuring that all cells in the square can be visited. Assume also that the border of the square is surrounded by a wall. In some cell of a particular maze, there's a robot. The robot understands four commands: L (Left), R (Right), U (Up), and D (Down). When given a command, it moves accordingly; if there's a “wall” in front, the robot stays in its position. How can one write a program for the robot to traverse all cells regardless of the maze's configuration and its initial position?
    Hint:

    Enumerate all initial states, which are defined by the maze and the robot's initial position. For each state, we shall write a program that serves as a continuation of the program developed for the preceding state.