Разделы 
Дополнительно
Задача по математике - 1936
2019-01-22 
На прямоугольном столе лежат равные картонные квадраты $n$ различных цветов со сторонами, параллельными сторонам стола. Если рассмотреть любые $n$ квадратов различных цветов, то какие-нибудь два из них можно прибить к столу одним гвоздем. Докажите, что все квадраты некоторого цвета можно прибить к столу $2n - 2$ гвоздями.
Решение:
Докажем утверждение задачи индукцией по количеству цветов $n$.
База для $n = 2$. Рассмотрим самый левый квадрат $K$. Если он первого цвета, то все квадраты второго цвета имеют с ним общую точку, следовательно, каждый квадрат второго цвета содержит одну из двух правых вершин квадрата $K$, следовательно, все квадраты второй системы можно прибить двумя гвоздями.
Индуктивный переход. Пусть мы доказали утверждение задачи для $n$ цветов, докажем для $(n + 1)$-го цвета. Рассмотрим все квадраты и выберем из них самый левый квадрат $K$. Пусть он покрашен в $(n + 1)$-ый цвет. Все квадраты, пересекающие $K$, содержат одну из двух его правых вершин, следовательно, их можно прибить двумя гвоздями. Уберем со стола все квадраты $(n + 1)$-го цвета и квадраты других цветов, пересекающие $K$. Остались квадраты $n$ различных цветов. Если теперь выбрать $n$ квадратов разных цветов, то среди них найдутся два пересекающихся (иначе добавим квадрат $K$ и получим $n + 1$ попарно не пересекающихся квадратов разных цветов, что противоречит условию задачи). Таким образом, по индуктивному предположению, можно выбрать один из цветов $i$ и прибить $2n - 2$ гвоздями все оставшиеся на столе квадраты этого цвета. Убранные квадраты цвета $i$ пересекают самый левый квадрат $K$, следовательно, эти квадраты можно прибить, забив два гвоздя в правые вершины квадрата $K$.
На прямоугольном столе лежат равные картонные квадраты $n$ различных цветов со сторонами, параллельными сторонам стола. Если рассмотреть любые $n$ квадратов различных цветов, то какие-нибудь два из них можно прибить к столу одним гвоздем. Докажите, что все квадраты некоторого цвета можно прибить к столу $2n - 2$ гвоздями.
Решение:
Докажем утверждение задачи индукцией по количеству цветов $n$.
База для $n = 2$. Рассмотрим самый левый квадрат $K$. Если он первого цвета, то все квадраты второго цвета имеют с ним общую точку, следовательно, каждый квадрат второго цвета содержит одну из двух правых вершин квадрата $K$, следовательно, все квадраты второй системы можно прибить двумя гвоздями.
Индуктивный переход. Пусть мы доказали утверждение задачи для $n$ цветов, докажем для $(n + 1)$-го цвета. Рассмотрим все квадраты и выберем из них самый левый квадрат $K$. Пусть он покрашен в $(n + 1)$-ый цвет. Все квадраты, пересекающие $K$, содержат одну из двух его правых вершин, следовательно, их можно прибить двумя гвоздями. Уберем со стола все квадраты $(n + 1)$-го цвета и квадраты других цветов, пересекающие $K$. Остались квадраты $n$ различных цветов. Если теперь выбрать $n$ квадратов разных цветов, то среди них найдутся два пересекающихся (иначе добавим квадрат $K$ и получим $n + 1$ попарно не пересекающихся квадратов разных цветов, что противоречит условию задачи). Таким образом, по индуктивному предположению, можно выбрать один из цветов $i$ и прибить $2n - 2$ гвоздями все оставшиеся на столе квадраты этого цвета. Убранные квадраты цвета $i$ пересекают самый левый квадрат $K$, следовательно, эти квадраты можно прибить, забив два гвоздя в правые вершины квадрата $K$.
