Question

Буратино связал 17 кукол мальвины лентами красного , синего и зеленого цвета так , что от каждой куклы к каждой другой кукле ведёт ровно одна лента . докажите , что найдутся три куклы , связанные одной лентой.

Answer 1

Это задача из теории графов. Можно представить, что куклы - это вершины графа, а ленты - это ребра, соединяющие вершины. Тогда граф получается полным, то есть каждая вершина соединена с каждой другой ребром. Кроме того, граф раскрашен в три цвета, то есть каждое ребро имеет один из трех цветов: красный, синий или зеленый. Нужно доказать, что в таком графе найдутся три вершины, соединенные ребрами одного цвета.

Для этого можно воспользоваться принципом Дирихле, который гласит, что если n предметов распределены по k ящикам, то хотя бы в одном ящике будет не меньше, чем ⌈n/k⌉ предметов, где ⌈x⌉ - это наименьшее целое число, большее или равное x.

Применим этот принцип к нашей задаче. Пусть ящики - это цвета лент, а предметы - это куклы. Тогда n = 17, а k = 3. По принципу Дирихле, хотя бы в одном ящике будет не меньше, чем ⌈17/3⌉ = 6 кукол. Это означает, что хотя бы 6 кукол связаны лентами одного цвета. Но тогда среди этих 6 кукол обязательно найдутся три, которые образуют треугольник, то есть связаны ребрами одного цвета. Это и есть наше доказательство.