Хирург оперирует вслепую по рентген-снимкам. Операция состоит из 20 действий, и каждое действие со­ вершается либо сверху, либо сбоку, либо спереди. Снимок можно сделать в любой момент опять же либо свер­ ху, либо сбоку, либо спереди. Снимок можно использовать только во время двух следующих действий после того, как он был сделан. Для дальнейших действий он считается негодным. Чтобы совершить очередное дей­ ствие, нужен годный снимок со сто­ роны, отличной от стороны действия (скажем, для действия сверху подой­ дёт снимок сбоку или спереди). Какого наименьшего числа снимков хирургу гарантированно хватит, если а) он будет узнавать до операции всю последовательность предстоящих 20 действий; б) он будет узнавать, какое следую­ щее действие понадобится, только по­ сле выполнения предыдущего?

Привет! Давай разберемся с этой интересной задачей.

а) Хирург знает всю последовательность действий заранее

В этом случае хирург может спланировать свои действия оптимально. Ему нужно обеспечить наличие "годного" снимка для каждой пары действий.

1. Рассмотрим первые два действия. Для них нужен снимок, сделанный перед первым действием.
2. Затем, для действий 3 и 4 нужен новый снимок, сделанный перед действием 3.
3. И так далее, каждые два действия требуют нового снимка.

Так как у нас 20 действий, то потребуется 20 / 2 = 10 снимков. Но! Нужно учесть, что для каждого действия нужен снимок с другой стороны. Значит, нужно чередовать стороны снимков.

Предположим, действия чередуются так: верх, бок, верх, бок, ...

Тогда схема снимков может быть такой:

• Снимок 1: Спереди (для действий 1 и 2)
• Снимок 2: Сбоку (для действий 3 и 4)
• Снимок 3: Спереди (для действий 5 и 6)
• Снимок 4: Сбоку (для действий 7 и 8)
• Снимок 5: Спереди (для действий 9 и 10)
• Снимок 6: Сбоку (для действий 11 и 12)
• Снимок 7: Спереди (для действий 13 и 14)
• Снимок 8: Сбоку (для действий 15 и 16)
• Снимок 9: Спереди (для действий 17 и 18)
• Снимок 10: Сбоку (для действий 19 и 20)

Таким образом, ответ: 10 снимков.

б) Хирург узнает следующее действие только после выполнения предыдущего

Здесь ситуация сложнее, так как хирург не может заранее спланировать, какой снимок ему понадобится. В худшем случае, ему придется делать снимок перед каждым действием.

Но, снимок "годен" для двух действий. Поэтому можно немного сэкономить. Представим, что каждое действие требует снимка с определенной стороны.

1. Действие 1: Нужен снимок перед действием 1.
2. Действие 2: Снимок, сделанный перед действием 1, еще "годен".
3. Действие 3: Нужен новый снимок. Снимок, сделанный перед действием 3, будет "годен" для действия 4.

И так далее. Получается, что снимок нужен перед каждым нечетным действием. Так как действий 20, то нечетных действий будет 10.

Однако, нужно учитывать, что сторона снимка должна отличаться от стороны действия. В худшем случае, хирург может столкнуться с тем, что ему придется делать снимок каждый раз, потому что предыдущий снимок не подходит по стороне.

Рассмотрим пример:

• Действие 1: Сверху. Хирург делает снимок сбоку.
• Действие 2: Сверху. Снимок сбоку еще "годен".
• Действие 3: Сверху. Снимок сбоку больше не "годен". Хирург делает снимок спереди.
• Действие 4: Сверху. Снимок спереди еще "годен".
• Действие 5: Сверху. Снимок спереди больше не "годен". Хирург делает снимок сбоку.

В худшем случае, все действия будут требовать снимка с одной и той же стороны, и тогда придется делать снимок перед каждым действием. Но снимок "годен" для двух действий, поэтому можно сократить количество снимков.

Давай подумаем, как это можно формализовать.

Пусть n - количество действий. Тогда количество необходимых снимков будет равно n, если каждый раз требуется снимок с определенной стороны и предыдущий снимок не подходит. Но так как снимок действует на два шага, мы можем сказать, что количество снимков примерно равно n / 2.

В нашем случае n = 20, поэтому 20 / 2 = 10. Однако это слишком оптимистично. Нужно рассмотреть худший случай.

Допустим, первые два действия требуют снимка сбоку или спереди. Хирург делает снимок сбоку. Следующие два действия снова требуют снимка сбоку или спереди. Хирург должен сделать новый снимок.

То есть, в худшем случае, на каждые два действия нужен новый снимок. Тогда получается 10 снимков. Но если бы снимок был годен только для одного действия, то потребовалось бы 20 снимков.

Рассмотрим такую стратегию: делать снимок перед каждым действием, но использовать предыдущий снимок, если он подходит.

• Действие 1: Сверху. Снимок: Сбоку.
• Действие 2: Сверху. Снимок: Спереди (предыдущий не подходит).
• Действие 3: Сверху. Снимок: Сбоку.
• ...
• Действие 20: Сверху. Снимок: ...

В таком случае, каждый раз нужен новый снимок. Но если бы мы знали следующие действия, то смогли бы сэкономить.

Так как хирург не знает следующие действия, он должен быть готов к худшему случаю. В худшем случае, для каждого действия потребуется новый снимок. Но так как снимок "годен" для двух действий, можно сократить количество снимков до 10. Но это если нам везет. А если не везет, и каждый раз требуется снимок с определенной стороны? Тогда нужно 20 снимков? Нет.

Предположим, что все действия требуют снимка сбоку. Тогда:

• Снимок 1: Сбоку (для действия 1 и 2)
• Снимок 2: Сбоку (для действия 3 и 4)
• ...
• Снимок 10: Сбоку (для действия 19 и 20)

То есть, в любом случае, 10 снимков достаточно.

Ответ: 10 снимков.