Помогите решить задачку с брейнгеймс)

jasd323

я время от времени для общего развития решаю задачки с брейнгеймс
и вот жётско застопорился вот на этой (решал в общей сложности уже 4 лекции, то есть часов 6 установил кучу фактов) практически решил для нечётных чисел, но, блин, я уверен, что решение это задачки должно быть довольно простым.
ах, да, сама задачка
Однажды 23 мегамозга решили сыграть в футбол. В процессе выбора команд они заметили интересную особенность: кого бы ни выбирали судьей матча, остальные 22 игрока могли разделиться на две команды по 11 человек с равным суммарным весом всех игроков. Известно, что вес каждого мегамозга выражался целым числом килограммов. Возможно ли такое, что не все мегамозги имели одинаковый вес?
Часа чрез полтора я практически уверился, что это невозможно.
Мб кого-то заинтересует, да и мне решение интересно будет посмотреть.

komBAR

Доказательство - индукцией по суммарному весу (веса считаем неотрицательными целыми (или вес может быть отрицательным? :o) когда сумма равна 0 - очевидно, что и веса все по нулю)
Очевидно, что четность у всех одинаковая. Если все четны - делишь пополам.
Если нечетны - вычитаешь у всех по единице, делишь пополам
ПРОФИТ!

Oxana-a

давай попробую, хотя мб я где-то налажал)
ПП.
Достаточно очевидно, что веса мозгов или все четные, или все нечетные. (b - вес каждой команды, a - вес первого судьи, c - 2го(произвольного) судьи. 2b-c+a кратно 2 => a-c кратно 2)
Пусть будут все четные. Докажем, что между их весами не может быть разница 2, 6 и тп. Опять ПП, пусть будут с разницей 2. Тогда, если мы сначала возьмем судьей первого, а потом отличного от него на 2, то вес команд изменится на 1. А это невозможно, потому что вес обязательно должен быть четным(как сумма четных). Для нечетных - аналогично. Продолжим для четных.
Докажем, что не может быть разница 4, 12 и тп. Просто поделим их веса на 2(задача от этого не меняется). Опять получатся четные/нечетные числа с разницей 2, 6 и тд, а мы уже доказали, что таких быть не может. Для нечетных - вычитаем 1 из всех весов, получаем четные - аналогично.
В итоге, мы так и будем уходить до бесконечной разницы(с разницей 2^n). Сойдет ли это для док-ва - хз =)
Ну вот нечто похожее я и написал =)

jasd323

ща копипастом вставлю в ответ
проверю, прокатит ли
но в целом я практически точно так и решал, но решение не приняли
Оставить комментарий
Имя или ник:
Комментарий: