Competition problem — Combinatorics

Library / /34 of 46

Combinatorics Difficulty 6.7 National olympiad Prove it Russia

On 11 sheets of paper 11 following statements are written (each sheet contains exactly one statement):
1) There are no sheets with false statements to the left of this sheet.
2) There is exactly 1 sheet with a false statement to the left of this sheet.
3) There are exactly 2 sheets with false statements to the left of this sheet.
...
11) There are exactly 10 sheets with false statements to the left of this sheet.

The sheets were put in a row (from the left to the right). After that some of the statements become true while the others become false. Find the greatest possible number of true statements.

(I. Rubanov)

Solution

Answer: 6.

If the sheets are arranged in the following order:

(for brevity, each sheet is marked with the number of false statements to its left), then there will be 6 true statements.

Let us show that there cannot be more. Suppose that two sheets with true statements are placed next to each other; then the number of sheets with false statements to the left of each of them is the same; this is impossible, since different numbers are written on these sheets. Therefore, among any two consecutive sheets, at least one statement is false. Thus, there are at least five sheets with false statements, since in each of the first five pairs there is a false one.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.