Browse · MathNet
PrintUkrainian Mathematical Olympiad
Ukraine counting and probability
Problem
Each of citizens of the Emerald city wears glasses (with two lenses). The lenses in the glasses are colored rose, blue and green evenly: in total there are lenses of each color. All citizens composed a circle so that no two neighbors in this circle have lenses of a common color. What is the maximum possible number of citizens wearing glasses with lenses of different color?
Solution
Будемо позначати кольори лінз літерами Р, Б, З. Зрозуміло, що в колі не можуть стояти поруч мешканці з різнокольоровими окулярами, тому таких мешканців не більше за . Якщо їх , то рівно двоє людей з однокольоровими окулярами стоять поруч (нехай це мешканці з лінзами РР та ББ), а далі по колу «різнокольорові» та «однокольорові» мешканці чергуються. Ліворуч та праворуч від зазначеної пари отримуємо кольори
..., РР, БЗ, РР, БЗ, РР, ББ, РЗ, ББ, РЗ, ББ, ...,
і при замиканні кола з'явиться пара сусідів або з лінзами однакового кольору, або ж — з однокольоровими окулярами в обох. Тому кількість є неможливою. Приклад з «різнокольоровим» мешканцем і вказаною кількістю лінз можна побудувати за схемою:
РР, БЗ, РР, БЗ, ..., БЗ, РР, ББ, РЗ, ББ, РЗ, ..., РЗ, ББ, ЗЗ, РБ, ЗЗ, РБ, ..., РБ, ЗЗ,
де останній, -ий, мешканець стає поруч із першим, а між виділеними мешканцями стоять по особи.
Відповідь: .
..., РР, БЗ, РР, БЗ, РР, ББ, РЗ, ББ, РЗ, ББ, ...,
і при замиканні кола з'явиться пара сусідів або з лінзами однакового кольору, або ж — з однокольоровими окулярами в обох. Тому кількість є неможливою. Приклад з «різнокольоровим» мешканцем і вказаною кількістю лінз можна побудувати за схемою:
РР, БЗ, РР, БЗ, ..., БЗ, РР, ББ, РЗ, ББ, РЗ, ..., РЗ, ББ, ЗЗ, РБ, ЗЗ, РБ, ..., РБ, ЗЗ,
де останній, -ий, мешканець стає поруч із першим, а між виділеними мешканцями стоять по особи.
Відповідь: .
Final answer
501
Techniques
Coloring schemes, extremal arguments