Đáp án bài toán xếp chỗ ngồi

Topic 51. EXTREMAL PRINCIPLE

Problem: There are 25 rows of seats in a hall, each row having 30 seats. If there are 680 people seated in the hall, at least how many rows have an equal number of people each?

Dịch đề: Một hội trường có 25 hàng ghế, mỗi hàng có 30 chiếc. Nếu có 680 người ngồi trong hội trường thì có ít nhất bao nhiêu hàng ghế có cùng số người ngồi?

Lời giải:

Có 680 người ngồi trên 25 x 30 = 750 ghế nên hội trường còn 70 chiếc ghế trống. Để ý rằng nếu hai hàng ghế bất kỳ có số người ngồi bằng nhau thì số ghế trống cũng bằng nhau. Ta sẽ chứng minh có ít nhất 4 hàng ghế có cùng số ghế trống.

Thật vậy, giả sử ngược lại, số các hàng có số ghế trống bằng nhau luôn nhỏ hơn 4.

Khi đó tổng số các ghế trống của 25 hàng không bé hơn:

3 x (0 + 1 + 2 + 3 + 4 + 5 + 6 + 7) + 8 = 92 > 70 (vô lý).

Tiếp theo chúng ta sẽ chỉ ra một cách sắp xếp 680 người vào 25 hàng ghế sao cho có ít nhất 4 hàng ghế có cùng số ghế trống (tức là có cùng số người ngồi).

Cách đơn giản nhất là xuất phát từ đẳng thức 4 x (0 + 1 + 2 + 3 + 4 + 5) + 10 = 70, suy ra có thể xếp 680 người ngồi sao cho có 24 hàng ghế chia thành 6 nhóm, mỗi nhóm có 4 hàng ghế lần lượt có số ghế trống là 0, 1, 2, 3, 4, 5 và hàng ghế thứ 25 có 10 ghế trống. Vậy có ít nhất 4 hàng ghế có cùng số người ngồi.

Đáp số là 4

Solution:

Since there are 680 people and 25 x 30 = 750 seats, there will be 70 empty seats. Note that if two rows have an equal number of people, then they also have an equal number of empty seats. We will prove that there are at least 4 rows with the same number of empty seats.

Indeed, if there are fewer than 4 rows with the same number of empty seats, then the total number of empty seats of all 25 rows will be no less than:

3 x (0 + 1 + 2 + 3 + 4 + 5 + 6 + 7) + 8 = 92 > 70 (contradictory).

Now we will present one way to arrange 680 people to 25 rows so that there are 4 rows with the same number of empty seats, i.e. the same number of people.

We have 4 x (0 + 1 + 2 + 3 + 4 + 5) + 10 = 70. Divide the 24 rows into 6 groups, where each group has 0, 1, 2, 3, 4, 5 empty seats respectively. The remaining 25th row will have 10 empty seats. Thus, there will be at least 4 rows with the same number of people.

The answer is 4.

Minh Phương