Варианты опроса учеников

Mapping the constraints

I’m identifying the constraints: no two adjacent students are called, and no more than two consecutive students remain uncalled.

Defining the sequence

I’m working on counting valid binary sequences of length 18 that avoid consecutive 1's and triple consecutive 0's. Establishing a recurrence relation is the next step.

Tracking sequences

I’m identifying valid sequences by their endings: '1', '0' with a single trailing 0, and '00' with two trailing 0's, establishing recurrence relations for each.

Establishing recurrence

I’m clarifying that b(n) is derived from sequences ending in '1'. For n=1, b(1) is '0', while a(1) and c(1) are 1 and 0 respectively.

Refining sequence rules

I’ve clarified recurrence relations: a(n) combines sequences ending in '0' or '00', b(n) forms from sequences ending in '1', and c(n) springs from sequences ending in '0' with run length 1.

Calculating valid sequences

OK, let me see. I’ve defined recurrence relations for sequences ending in '1', '0', and '00'. Summing these, I calculated the total valid sequences for n from 1 to 18, arriving at S(18)=265.

Thought about варианты проведения опроса pendant 18 secondes

Нам нужно сосчитать количество способов выбрать подмножество из 18 учеников (каждому ученику ставим «вызван» = 1 или «не вызван» = 0) так, чтобы:

1. Не было двух подряд вызванных (то есть в последовательности не встречалось "11").
2. Не было трёх подряд невызванных (то есть не встречалось "000").

Иными словами, мы считаем количество бинарных последовательностей длины 18 без подряд идущих единиц и без трёх подряд идущих нулей.

Идея решения через динамику

Обозначим через $S(n)$ количество таких «хороших» последовательностей длины $n$. Удобно ввести более тонкое разбиение:

• $a(n)$ — число хороших последовательностей длины $n$, заканчивающихся на $1$;
• $b(n)$ — число хороших последовательностей длины $n$, заканчивающихся на $0$, причём в конце стоит ровно один ноль (то есть последний фрагмент $\dots 10$);
• $c(n)$ — число хороших последовательностей длины $n$, заканчивающихся на $00$ (то есть последний фрагмент $\dots 100$).

Заметим, что трёх нулей подряд быть не может (это запрещено), поэтому ситуации $\dots 000$ мы в отдельных состояниях не учитываем: такие последовательности недопустимы.

Тогда общее число хороших последовательностей длины $n$ равно

Как переходить между состояниями

Рассмотрим, из каких состояний могут получаться другие при добавлении ещё одного символа (0 или 1) к «хвосту»:

1. $a(n)$ (заканчивается на $1$) может получиться, если в $(n-1)$-ой позиции был ноль (один или два). Значит,

   $$a(n) = b(n - 1) + c(n - 1).$$

   (Из $a(n-1)$ перейти нельзя, так как это дало бы две подряд идущие единицы.)

2. $b(n)$ (заканчивается на одинарный $0$) может получиться, если предыдущая последовательность закончилась на $1$. Значит,

   $$b(n) = a(n - 1).$$

3. $c(n)$ (заканчивается на $00$) может получиться, если предыдущая последовательность закончилась на одинарный ноль $b(n-1)$. Тогда мы добавляем ещё один ноль:

   $$c(n) = b(n - 1).$$

Таким образом, получаем систему рекуррентных соотношений:

Базовые случаи

Для $n = 1$:

• $a(1)$ — последовательности длины 1, оканчивающиеся на $1$. Такая всего одна: $[\,1\,]$. Значит $a(1) = 1$.
• $b(1)$ — последовательности длины 1, оканчивающиеся на $0$, и там ровно один ноль. Это $[\,0\,]$. Значит $b(1) = 1$.
• $c(1)$ — последовательности длины 1, заканчивающиеся на $00$. Это невозможно, значит $c(1) = 0$.

Тогда

Далее аккуратно считаем по рекурсиям:

$n = 2$

• $a(2) = b(1) + c(1) = 1 + 0 = 1$,
• $b(2) = a(1) = 1$,
• $c(2) = b(1) = 1$,
• $S(2) = a(2) + b(2) + c(2) = 1 + 1 + 1 = 3$.

$n = 3$

• $a(3) = b(2) + c(2) = 1 + 1 = 2$,
• $b(3) = a(2) = 1$,
• $c(3) = b(2) = 1$,
• $S(3) = 2 + 1 + 1 = 4$.

Дальше можно либо продолжать вручную, либо (что проще на экзамене/контрольной) аккуратно «прогнать» эти соотношения. Ниже таблица значений:

Из последней строки видно, что для $n=18$:

Ответ: $\boxed{265}$.