На скамейке сидело двое учеников из разных школ. Д...

Domanda

На скамейке сидело двое учеников из разных школ. Далее к ним в каком-то порядке подошли 770 учеников тех же школ и сели на скамейку (каждый новоприбывший садился с краю или между какими-то двумя детьми). В конце оказалось, что никакие два одношкольника не сидят рядом. Сколько учеников, приходя, садились между двумя ребятами из дружественной школы?

Pensiero

Solving a combinatorics problem

We're dealing with a problem where two schools' students alternate seats on a bench, with no two students from the same school sitting next to each other. The goal is to count how many students sit between two students from the other school (i.e., sitting between two of the opposite school). This requires considering how the students arrive and sit in a way that satisfies the "no adjacent same-school" rule.

Counting student arrangements

We have a total of 772 students (2 initial + 770 arrivals). In the final arrangement, students will alternate between the two schools. We are asked to count how many students sit between two from the other school. For an arrival to sit between two students of the different school, there must already be two adjacent students from the opposite school before the arrival.

Counting seat insertions

To sit between two students of the opposite school, there must already be an adjacent pair of students from that school. For instance, if an "A" is inserted between two "B"s, it creates a "B A B" sequence. The key question is how many arrivals eliminate adjacent same-school pairs by sitting between them. This involves counting changes in adjacent pairs.

Defining adjacency changes

Let's define the number of monochromatic adjacencies (pairs of students from the same school) after each arrival. Initially, with two students (AB), there are zero adjacencies. When a student sits at the end, an adjacency can form, increasing or maintaining the count based on whether the new student is from the same or opposite school. Sitting between two students alters the adjacencies, reducing the count if it breaks a same-school pair.

Tracking adjacency changes

We're counting types of insertions that create "bad edges" — where a monochrome adjacency is created and must be later removed. Insertions at ends with same-school students create a bad edge, as do insertions between different schools. Only target insertions (between same-school pairs of opposite school) remove these bad edges. The total number of such insertions is the target count (a).

Tracking student insertion patterns

The problem is tied to how students' seating preferences impact monochrome adjacencies and "blocks" (runs of students from the same school). Total blocks started at two, and post-arrivals, the count rises to 772. The total number of insertions can help determine how many "bad edges" are created, and these values can be used to find the target count (a).

Analyzing seating patterns

The seating arrangement is tightly controlled by the rules—only alternating school blocks are allowed under the final setup. The analysis concludes that there was no insertion between two same-school students, as that would violate the alternating condition. Essentially, every student insertion was either at an endpoint or split a mixed block. The final answer is zero for students seated between two from the "friendly" school.

Verifying block changes

The analysis concludes that the total increase in blocks equals 770, derived from end-other and between-same-other moves. Since zero-change moves don't contribute to block counts, B, C, and E must sum to zero. The only valid operations are end-other and between-same-other, ensuring a maximum of 770 changes.

Thought for 2m 34s

Risposta

Ответ: 0.

Короткое рассуждение через “блоки” (максимальные подряд идущие ученики одной школы).

В начале было 2 блока: $A|B$ .
В конце, когда одинаковые не сидят рядом, каждый ученик — отдельный блок длины 1, т.е. всего $772$ блока. Значит, число блоков увеличилось на $772-2=770$ .

Как влияет посадка:

На краю рядом с учеником другой школы — число блоков увеличивается на $+1$ .
Между двумя учениками одной школы:
- если сажаем ученика другой школы, блок той школы делится на два, а у новой школы появляется новый блок: суммарно $+2$ ;
- если сажаем ученика той же школы — число блоков не меняется ( $+0$ ).
Между учениками разных школ — число блоков не меняется ( $+0$ ).
На краю рядом с учеником той же школы — тоже $(+0)$ .

Обозначим:

$x$ — сколько раз сели на край рядом с учеником другой школы ( $+1$ );
$a$ — сколько раз сели между двумя учениками дружественной (другой) школы ( $+2$ ) — это и спрашивается.

Тогда по приросту блоков:

x + 2a = 770. \quad (1)

Теперь посчитаем порознь для каждой школы. Изначально у каждой школы по одному блоку, в конце — по $386$ . Прирост блоков каждой школы даёт только:

посадка на край ученика этой школы рядом с другой школой ( $+1$ );
посадка этой школы между двумя учениками другой школы ( $+1$ ).

Значит, для каждой школы прирост $=385$ . В сумме для двух школ получаем:

x + a = 770. \quad (2)

Из (1) и (2):

(x+2a) - (x+a) = a = 0.

Следовательно, никто не садился между двумя учениками дружественной школы.