Track / Stage 6 / 143 of 400 #1143 of 2000

Problem 1143

National olympiad, first round

Combinatorics Difficulty 6.2 Find the answer

Students in a school are arranged in an order that when you count from left to right, there will be $n$ students in the first row, $n-1$ students in the second row, $n - 2$ students in the third row,... until there is one student in the $n$ th row. All the students face to the first row. For example, here is an arrangement for $n = 5$ , where each $*$ represents one student:
$*$
$* *$
$* * *$
$* * * *$
$* * * * *$ (first row)

Each student will pick one of two following statement (except the student standing at the beginning of the row):
i) The guy before me is telling the truth, while the guy standing next to him on the left is lying.
ii) The guy before me is lying, while the guy standing next to him on the left is telling the truth.

For $n = 2015$ , find the maximum number of students telling the truth.
(A student is lying if what he said is not true. Otherwise, he is telling the truth.)

Your answer

Official solution

1. Understanding the Problem:
- We have $n$ rows of students.
- The first row has $n$ students, the second row has $n-1$ students, and so on until the $n$ -th row which has 1 student.
- Each student (except the first in each row) can make one of two statements:
1. The student in front of me is telling the truth, and the student to their left is lying.
2. The student in front of me is lying, and the student to their left is telling the truth.
- We need to find the maximum number of students telling the truth for $n = 2015$ .

2. Analyzing the Statements:
- Let's denote the students in the $i$ -th row as $S_{i,1}, S_{i,2}, \ldots, S_{i,i}$ .
- The first student in each row $S_{i,1}$ does not make any statement.
- For $S_{i,j}$ where $j > 1$ , the statements are about $S_{i-1,j-1}$ and $S_{i-1,j}$ .

3. Pattern of Truth and Lies:
- We need to determine a pattern that maximizes the number of students telling the truth.
- Consider the first row: all students can be assumed to be telling the truth since there are no students in front of them to contradict this.

4. Inductive Approach:
- Assume we have a pattern for the first $k$ rows.
- For the $(k+1)$ -th row, we need to decide the truthfulness of each student based on the statements they can make about the $k$ -th row.

5. Constructing the Pattern:
- Let's start with the first few rows to identify a pattern:
- Row 1: $T, T, T, \ldots, T$ (all true)
- Row 2: $T, T, T, \ldots, T$ (all true)
- Row 3: $T, T, T, \ldots, T$ (all true)
- Continue this pattern until we find a contradiction or a better pattern.

6. Generalizing the Pattern:
- If we assume all students in the first row are telling the truth, then the second row can also be all true.
- This pattern can continue until the $n$ -th row.

7. Calculating the Maximum Number of Truthful Students:
- The total number of students is the sum of the first $n$ natural numbers:
$\text{Total students} = \sum_{i=1}^{n} i = \frac{n(n+1)}{2}$
- For $n = 2015$ :
$\text{Total students} = \frac{2015 \times 2016}{2} = 2031120$

8. Conclusion:
- If all students can be assumed to be telling the truth without contradiction, then the maximum number of students telling the truth is the total number of students.

The final answer is $\boxed{2031120}$

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.