Часто в задаче на доказательство используется чётность какого-либо параметра.
Классический пример: Существует ли группа из 11 человек, в которой у каждого есть трое знакомых?
Допустим, мы захотим изобразить людей точками, а знакомства - линиями, соединяющими пары точек. Сколько всего линий будет проведено? Из каждой из 11 точек должно выйти по 3 линии, итого 33.
Но ведь при таком методе подсчёта каждая линия будет подсчитана дважды, значит, этот результат нужно разделить на 2. А 33 на 2 не делится. Следовательно, ситуация, описанная в условии, невозможна.
Здесь, кроме чётности, используются также методы теории графов.
Классический пример: Существует ли группа из 11 человек, в которой у каждого есть трое знакомых?
Допустим, мы захотим изобразить людей точками, а знакомства - линиями, соединяющими пары точек. Сколько всего линий будет проведено? Из каждой из 11 точек должно выйти по 3 линии, итого 33.
Но ведь при таком методе подсчёта каждая линия будет подсчитана дважды, значит, этот результат нужно разделить на 2. А 33 на 2 не делится. Следовательно, ситуация, описанная в условии, невозможна.
Здесь, кроме чётности, используются также методы теории графов.
Хорошее док-во. Пригодится на олимпиадах)
ОтветитьУдалить