Обходы и подсчёты

1. В 1905 году был построен Императорский мост, который позже был разрушен бомбардировкой во время Второй мировой войны. Существует легенда о том, что этот мост был построен по приказу самого кайзера, который стал жертвой шутки учёных, бывших на светском приёме. Но, император не растерялся и сказал, что решит эту задачу за одну минуту: для этого ему нужны всего лишь перо и карта города. Ученые даже опешили от такого ответа, но принесли все. Император взял перо и нарисовал еще один мост между островом Ломзе и Форштадтом, сказав: «Повелеваю построить здесь восьмой мост города». На его опорах в 2005 году был построен Юбилейный мост. Изобразите граф мостов и придумайте какой-нибудь способ обхода, добавив 8-й мост там же, где его повелел построить император (Форштадт на схеме внизу реки):

→

2. В шахматном турнире по круговой системе (каждый играет с каждым) участвовало 10 человек. Сколько партий они сыграли друг с другом и сколько сыграл каждый?

3. Может ли в стране, в которой из каждого города выходит ровно три дороги, быть ровно 100 дорог?

4. Докажите лемму о рукопожатиях: в любом графе число вершин нечётной степени всегда чётно, а сумма степеней всех вершин равна удвоенному числу рёбер.

5. В графе каждая вершина покрашена в синий или зеленый цвет. При этом каждая синяя вершина связана с пятью синими и десятью зелеными, а каждая зеленая с девятью синими и шестью зелеными. Каких вершин больше – синих или зеленых?

6. 100 замов получили взыскания от 100 завов. При этом каждый зав наложил по одному взысканию на 15 замов, а каждый зам получил по одному взысканию от 15 завов. Докажите, что директор может снять часть взысканий так, что у каждого зама останется по одному взысканию, и все взыскания будут наложены разными завами.

7. Среди n рыцарей каждые двое – либо друзья, либо враги. У каждого из них ровно 3 врага, причём враги его друзей являются его врагами. При каких n такое возможно?

8. В классе каждый мальчик дружит с тремя девочками, а каждая девочка – с четырьмя мальчиками. 17 из них любят играть в матбой, и в классе 13 столов (за столом сидит 1 или 2 человека). Сколько всего ребят в классе?

9. Артём по одному выставляет королей на шахматную доску, записывая для каждого, сколько ранее выставленных королей он побил. Доска заполнилась. Докажите, что сумма выписанных чисел не зависит от порядка выставления. Чему она равна?

10. В строку выписано 11 целых чисел. Для любой группы подряд идущих чисел подсчитана ее сумма (группы из одного числа тоже учитывались). Какое наибольшее количество сумм могло оказаться нечетными?

Поиск по сайту: