## Task A-1.3.

On $n$ cards, the following sentences are written:

"At least $k$ sentences to the left of this card are false."

for $k=0,1,2, \ldots, n-1$. The cards are arranged in some order from left to right. What is the maximum number of sentences that can be true?
## Solution.

We will show that at most $\left\lfloor\frac{n+1}{2}\right\rfloor$ statements can be true, i.e., for an even number $n=2 m$ at most $m=\frac{1}{2} n$, and for an odd number $n=2 m-1$ at most $m=\frac{n+1}{2}$.

A card that says "At least $k$ statements to the left of this card are false" is called a "card $k$". We will also say "card $k$ is false (true)" instead of "the statement on card $k$ is false (true)".

If we arrange the cards in the order: $0, n-1,1, n-2,2, \ldots$, then the statements on the first, third, fifth, ... cards are true, and the statements on the other cards are false. In this arrangement, there are exactly $\left\lfloor\frac{n+1}{2}\right\rfloor$ true cards.

Now we will prove that no more than $\left\lfloor\frac{n+1}{2}\right\rfloor$ cards can be true.

Let $n=2 m$ or $n=2 m-1$.

If card $k$ for some $k \geqslant m$ is true, then there are at least $k$ false cards (even among those to the left of it). This means there are at least $m$ false cards, or at most $n-m \leqslant m$ true cards.

Otherwise, all cards for $k>m$ are false, so there are at most $m$ true cards.