В классном журнале записаны по алфавиту фамилии 18 учеников. Когда учитель проводит…
- User
В классном журнале записаны по алфавиту фамилии 18 учеников. Когда учитель проводит опрос, он вызывает некоторых учеников. Учитель никогда не вызывает двух учеников, чьи фамилии записаны подряд. Но среди невызванных не бывает больше двух учеников, чьи фамилии записаны подряд. Сколько разных вариантов существует для проведения опроса?
- Assistant
To solve this problem, we will consider all possible sequences of calls and non-calls for the 18 students, respecting the given constraints:
- No two called students (C) are adjacent.
- Among the non-called students (N), there cannot be more than two in a row.
We'll model this problem using dynamic programming by defining the following states based on the last positions in the sequence:
- State 0: The sequence ends with a called student (C).
- State 1: The sequence ends with one non-called student (N).
- State 2: The sequence ends with two non-called students (NN).
We will use arrays ( f0[n] ), ( f1[n] ), and ( f2[n] ) to represent the number of sequences of length ( n ) that end with state 0, 1, and 2, respectively.
Recurrence Relations:
- ( f0[n+1] = f1[n] + f2[n] ) (We can place a C after one or two Ns)
- ( f1[n+1] = f0[n] ) (We can place an N after a C)
- ( f2[n+1] = f1[n] ) (We can have two Ns if the previous state was one N)
Initial Conditions:
- ( f0[0] = 1 ) (An empty sequence can be considered as ending with a C)
- ( f1[0] = 0 )
- ( f2[0] = 0 )
Computation:
We compute the values step by step up to ( n = 18 ):
-
For ( n = 1 ):
- ( f0[1] = f1[0] + f2[0] = 0 )
- ( f1[1] = f0[0] = 1 )
- ( f2[1] = f1[0] = 0 )
-
For ( n = 2 ):
- ( f0[2] = f1[1] + f2[1] = 1 )
- ( f1[2] = f0[1] = 0 )
- ( f2[2] = f1[1] = 1 )
...and so on, up to ( n = 18 ).
Final Calculation:
At ( n = 18 ):
- ( f0[18] = 65 )
- ( f1[18] = 49 )
- ( f2[18] = 37 )
Total Number of Sequences:
( \text{Total} = f0[18] + f1[18] + f2[18] = 65 + 49 + 37 = 151 )
Answer:
151