Процессы и алгоритмы

Назовем человека, сидящего напротив Васи, Андреем. Сначала приведем пример, при котором меньше, чем печенек может не хватить. Пусть у Андрея печенек. Расставим людям веса, начиная от Андрея, у которого вес будет равен и идя по двум дугам к Васе, умножая вес очередного человека на (тем самым у Васи будет вес

Умножим вес каждого человека на количество печенек у него, и сложим эти числа у всех людей. Посчитанную сумму обозначим через Заметим, что при описанной в условии операции сумма не увеличивается. Изначальная сумма меньше Но если бы Васе досталась печенька, сумма стала бы не меньше что невозможно.

Теперь покажем, что печенек всегда хватит. Также расставим веса и будем считать сумму Рассмотрим две дуги и между Андреем и Васей, включая их обоих. Посчитаем отдельно две суммы для дуг и Заметим, что печеньки Андрея будут посчитаны дважды, а вес каждого другого человека не меньше Поэтому, если печенек хотя бы то в сумме на дугах и получится не меньше значит, хотя бы на одной из дуг сумма будет не меньше Не умаляя общности скажем, что это дуга

Пока на дуге есть люди, у которого хотя бы две печеньки, будем заставлять их съедать одну печеньку и отдавать вторую соседу, который сидит ближе к Васе (или самому Васе). Заметим, что, во-первых, при такой операции сумма на дуге не меняется, во-вторых, уменьшается общее количество печенек, поэтому операции не могут продолжаться бесконечно долго. Если Васе в итоге не досталось печенек, то сумма на дуге не превосходит что не верно. Поэтому Васе обязательно достанется печенька.