Графы

[kati]

Помогите, пж, решить!!!
1) В шахматном турнире в один круг все участники кроме Пети набрали одинаковое число очков. Доказать, что Петя либо все партии выиграл, либо все проиграл?
2) На курсе 50 студентов. Известно, что среди любых четырех студентов имеется хотя бы один студент, знакомый с тремя остальными. Доказать,что найдется студент, знакомый со всеми.
3) На плоскости нарисованы 100 окружностей. Доказать, что карту, образованную при их пересечении, можно раскрасить двумя цветами.

[Sonic86]

(Оффтоп)

1) а что такое шахматный турнир в 1 круг???

2) Если не ошибаюсь, можно для любого $n \geq 4$ по индукции доказать, что граф, удовлетворяющий описанному условию, полный, а значит все понятно.
3) Можно по индукции и без графов доказать для любого числа окружностей. Если делать через графы, то по идее надо так: каждому куску плоскости ставим в соответствие вершину графа, если 2 куска смежны по дуге окружности - рисуем ребро между соответствующими вершинами. И можно попытаться интерпретировать процедуру добавления окружности как процедуру преобразования графа. Ну и рассмотреть граф и для него тоже по индукции доказать

[Toucan]

Тема перемещена в Карантин.

Чтобы оттуда выбраться, приведите свои попытки решения задач (или хоть какие-нибудь соображения).

После того как исправите сообщение, сообщите об этом в теме Сообщение в карантине исправлено.