Bogdanov I.I.

In a store, 21 white and 21 purple shirts are hanging in a row. Find the smallest $k$ such that for any initial order of the shirts, it is possible to remove $k$ white and $k$ purple shirts so that the remaining white shirts hang together and the remaining purple shirts also hang together.
First, let's show that \( k \), equal to 10, is sufficient.

First method. We will walk along the row of shirts and count the white and purple shirts separately. As soon as we count 11 of one color - let's assume, without loss of generality, purple - shirts, we will stop. Now we will remove all the white shirts that we have passed (there are no more than 10), and all the purple shirts that we have not yet reached (there are exactly 10). If necessary, we will remove a few more white shirts. It is obvious that all 11 purple shirts are hanging in a row (all the white shirts that were between them have been removed). The remaining white shirts also hang in a row: all the remaining purple shirts have been removed.

Second method. We will stand between the 21st and 22nd shirt, then there will be 21 shirts on both the left and the right. Without loss of generality, we can assume that there are no more white shirts on the left than purple ones. Then there are no more than 10 white shirts on the left, and no more than 10 purple shirts on the right (because there should be as many purple shirts as there are white ones on the left). We will remove all the white shirts on the left and all the purple shirts on the right. After this, all the remaining purple shirts will be hanging on the left, and all the remaining white ones on the right. If we removed \( n \) shirts, the problem 64770 Topics: [ Proof by contradiction ]  \([ \quad \underline{\text{ Induction (other) }} \quad]\)  Difficulty: 4  Classes: 9, 10, 11  Author: Khrrabrov A.  Given a function \( f \), defined on the set of real numbers and taking real values. It is known that for any \( x \) and \( y \), such that \( x > y \), the inequality \( (f(x))^2 \leq f(y) \) holds. Prove that the set of values of the function is contained in the interval \([0,1]\).

## Solution

By the condition \( f(y) \geq (f(y+1))^2 \geq 0 \) for any \( y \), so all values of the function are non-negative.

Now let \( f(x_0) = 1 + a > 1 \) for some \( x_0 \). We will prove by induction on \( n \) that \( f(y) > 1 + 2^n a \) for any \( y < x_0 \).

Base case. For \( n = 0 \), \( f(y) > 1 + 2^0 a = 1 + a \).

Inductive step. Assume \( f(y) > 1 + 2^n a \). Then \( f(y) \geq (f(\frac{1}{2}(x_0 + y)))^2 = 1 + 2^{n+1} a + (2^n a)^2 > 1 + 2^{n+1} a \).

Thus, for any fixed \( y < x_0 \), \( f(y) > 1 + 2^n a \) for any natural \( n \). But this is impossible, as \( 2^n a > f(y) \) for sufficiently large \( n \). Contradiction.