Конференция, чётность/нечётность

Разминка для мозгов » Задачи » Конференция, чётность/нечётность

Добавлено: 13.01.15 в 17:15

Доказать, что число участников конференции, знакомых с нечетным числом участников, четно.

Переформулируем задачу на языке математики. Имеется конечное число точек (участники конференции). Некоторые пары этих точек соединены отрезками (знакомства). Нужно доказать, что число точек, соединенных с нечетным числом точек, четно.

Поставим на каждом отрезке 2 стрелки, направленные в те 2 точки, которые соединяет отрезок. Число всех стрелок окажется чётным = число отрезков * 2. А теперь посчитаем количество стрелок по-другому. Сначала посчитаем стрелки около каждой точки, а потом найденные числа сложим. Должно получиться тоже самое число. Но если число точек, в которые направлено нечетное количество стрелок, нечетное, то вся сумма будет нечетная, что невозможно.

ПОКАЗАТЬ РЕШЕНИЕ/ОТВЕТ

источник

Комментарии

Google says:

Рустам (27.03.15):

Можно доказать и так (только нужно уточнить, что понятие "знаком" обладает свойством дву-направленности - "если А знает Б, то и Б знает А"):

итак ... назовем "четкниками" - тех, кто знаком с четным числом участников, а "нечетниками" - кто знаком с нечетным числов учеастников.

Естественно, что

<Сумма_всех_знакомств_четников> + <Сумма_всех_знакомств_нечетников> = <Сумма_всех_знакомств_на_конференеции>
или можно записать так:

<Сумма_всех_знакомств_нечетников> = <Сумма_всех_знакомств_на_конференции> - <Сумма_всех_знакомств_четников>

При этом,
1) <Сумма_всех_знакомств_четников> - четная (ведь каждый из четников знает четное число участников - а сколько не складывай только четные числа - всегда получится четное число)

2) В силу "обоюдной направленности" отношение "знакомство", <Сумма_всех_знакомств_на_конференции> - также четное число - поскольку "если А знает Б, то и Б знает А" - а значит общее число знакомств всегда четно

Следовательно, Сумма_всех_знакомств_нечетников представляет собою разность двух четных чисел и должно быть четным числом (или нулем)

		Сборник задач разного уровня сложности по математике, информатике, физике, химии, программированию, экономике etc. Логические задачи, SQL задачи, решение задач. Задачи с ответами, а также нерешённые задачи. Petruchek.Info

Petruchek.Info

Конференция, чётность/нечётность