№ 76 ЗПС = № 76 ЗПС
На полиці стоять підряд 50 книжок, частина — з фізики, частина — з математики. Відомо, що жодна книжка з фізики не стоїть поряд з іншою книжкою з фізики, а кожна книжка з математики обов’язково стоїть поряд з іншою книжкою з математики. Якою може бути найбільша кількість книжок з фізики?
Розв’язок:
Нехай $F$ — книжка з фізики, $M$ — книжка з математики.
За умовою, жодні дві $F$ не стоять поруч, а кожна $M$ має сусідню $M$. Це означає, що книжки з математики мають стояти групами по $2$ або більше (наприклад, $MM$, $MMM$ тощо).
Щоб максимізувати кількість $F$, треба мінімізувати кількість $M$ у кожній групі. Найменша група $M$, що задовольняє умову — це $MM$.
Отже, оптимальна розстановка має вигляд блоків $FMM$.
Один блок $FMM$ займає $3$ місця і містить одну книжку з фізики.
Розділимо $50$ на $3$:
$50=16\cdot3+2$
Це означає, що ми можемо розмістити $16$ блоків $FMM$ (це $48$ книжок), після чого залишається $2$ місця. Щоб додати ще одну книжку з фізики, ми можемо закінчити ряд послідовністю $FMM...F$.
Наприклад: $(FMM)\cdot16+F=48+1=49$ книжок. Залишається ще одна книжка, яка має бути $M$, щоб задовольнити умову для останньої $F$.
Таким чином, розстановка виглядає як $17$ книжок з фізики та $33$ книжки з математики (наприклад, $FMMFMM...FMMF$).
Усього $17+33=50$ книжок. Умова виконується.
Відповідь:
$17$.