Пете необходимо спаять электрическую схему, состоящую из 10 чипов, соединённых между собой проводами (один провод соединяет два различных чипа; два чипа может соединять не более одного провода), при этом из одного чипа должно выходить 9 проводов, из одного — 8, из одного — 7, из двух — по 5, из трёх — по 3, из одного — 2, из одного — 1. Может ли Петя спаять такую схему?
Решение 1 (детское).
Если из какого-то чипа выходит 9 проводов, то они идут ко всем остальным чипам. Посмотрим на схему из оставшихся девяти чипов. Из них выходит 7, 6, 4, 4, 2, 2, 2, 1, 0 проводов соответственно.
На последний чип можем больше не смотреть, потому что проводов из неё не выходит.
Осталось восемь чипов, из которых выходит 7, 6, 4, 4, 2, 2, 2, 1 проводов.
Раз из какого-то выходит семь проводов, значит, они идут ко всем остальным. Проведём их и "забудем" ещё и этот чип.
Из оставшихся выходит 5, 3, 3, 1, 1, 1, 0 проводов. "Забудем" теперь чип, из которого выходит 0 проводов.
Останется шесть чипов, из которых выходит 5, 3, 3, 1, 1, 1 проводов. Среди них есть тот, от которого идут провода ко всем оставшимся. Проведём их и "забудем" очередной чип.
Останется пять чипов, из которых выходит 2, 2, 0, 0, 0 проводов. Оказывается, что останутся два чипа, которые должны быть соединены двумя проводами, а этого быть не может!
Решение 2 (немного счёта).
Рассмотрим пять чипов, из которых выходит больше всего проводов.
Сумма равна 9+7+6+5+5=34. Но ведь провода могут идти и между этими пятью чипами. И тогда они будут считаться два раза (ведь у каждого провода, как и у каждой палки, два конца). Больше 5*4 точно не посчитается.
А когда могут идти остальные (34-20=14) провода? Только к оставшимся пяти чипам. Но от них идёт максимум 3+3+3+2+1=12 проводов. Получаем противоречие!