Problem

Source: All-Russian MO 2009 Regional 9.5

Tags: combinatorics



There are $11$ phrases written on $11$ pieces of paper (one per sheet): 1) To the left of this sheet there are no sheets with false statements. 2) Exactly one sheet to the left of this one contains a false statement. 3) Exactly $2$ sheets to the left of this one contain false statements ... 11) Exactly $10$ sheets to the left of this one contain false statements. The sheets of paper were laid out in some order in a row, going from left to right. After this, some of the written statements became true and some became false. What is the greatest possible number of true statements?