Мат сауаттылық. Ответы на логические задачи, опубликованные в 1(25), 2011 г. Эйлеровы графы
 Скачать 154.83 Kb.
|
|
М АТ Е М АТ И К А ЖАС ТАЛАП-KZ №2(26), июнь 2011 20 Ответы на логические задачи, опубликованные в № 1(25), 2011 г. Эйлеровы графы Для того чтобы нарисовать любой граф, не отрывая руки от бумаги и не проводя дважды по одной и той же линии, необходимо в каждую вершину войти столько же раз, сколько и выйти, кроме начальной и ко- нечной. Поэтому степени всех вершин нарисованного графа, кроме начальной и конечной, должны быть четными. Граф должен иметь не более двух не- четных вершин. Значит первый и второй граф, изображенные на рис. 1, можно изобразить, а тре- тий нет. Три мудреца Рассуждения третьего мудреца: «На мне белого колпака быть не может, поскольку иначе бы второй мудрец смог определить цвет своего колпака. Но он этого не сделал, значит на мне черный колпак». Предположим, что на C белый колпак, тогда второй мудрец мог рассуждать так: «На мне белого колпака быть не может, поскольку иначе первый мудрец A , увидев два белых колпака и зная, что белых колпака всего два, сразу определил бы цвет своего колпака. Но он этого не сделал, значит на мне черный колпак». 1000 привидений Перебирая частные случаи, находим, что шкафы с номерами 1, 4, 9, 16, … останутся от- крытыми. Возникает предположение, что шкаф останется открытым, если его номер являет- ся квадратом натурального числа. Заметим, что шкаф с номером n меняет состояние столько раз, сколько делителей у числа n . При этом шкаф окажется в итоге открытым, если n имеет нечетное число делителей. Однако делители образуют пары, если d – делитель числа n , то d n – также является делителем. Поэтому количество делителей будет нечетно лишь тогда, когда для какого-то d выполняется равенство d n d или 2 d n , то есть чис- ло n является полным квадратом. Квадраты не превосходящие 1000 – это 2 2 2 31 2 1 ..., , , Значит, всего 31 шкаф останется открытым. Телефонные линии А) Ответ: нельзя. Предположим, что это возможно. В этом графе 15 вершин, степень каждого из которых равна семи, так как каждый телефон соединен с семью другими. Подсчитаем количество ребер (линия, соединяющая два телефона) в этом графе. Для этого сначала просуммируем степени всех его вершин. Ясно, что при таком подсчете каждое ребро учтено дважды (оно ведь соединяет две вершины). Поэтому число ребер графа должно быть равно 2 7 15 , но это число нецелое. Следовательно, такого графа не существует, а значит, и соединить те- лефоны требуемым образом невозможно; Б) Ответ: нельзя. Рассуждая аналогично, количество ребер должно быть равно 2 5 3 6 8 3 4 . Но это число нецелое. Следовательно, соединить телефоны требуемым образом также нельзя. |