 |
|
 |
 |
 | Карта сайта |
 | Недавние изменения |
 | Поиск |
 | Вы посетили |
 | История страницы |
 | Вход |
Различия
Здесь показаны различия между двумя версиями данной страницы.
|
marathon:problem_116 [2019/05/25 22:00] letsko |
marathon:problem_116 [2019/05/30 21:15] (текущий) letsko |
||
|---|---|---|---|
| Строка 39: | Строка 39: | ||
| б) Докажем, что множество требуемых графов бесконечно. | б) Докажем, что множество требуемых графов бесконечно. | ||
| Для этого укажем алгоритм построения бесконечной серии подходящих графов. | Для этого укажем алгоритм построения бесконечной серии подходящих графов. | ||
| - | Легко убедиться, что дерево, у которого 10 вершин являются висячими, а три остальных имеют степени 3, 4, 4, | + | Легко убедиться, что дерево, у которого 7 из 10 вершин являются висячими, а три остальных имеют степени 3, 4, 4, |
| удовлетворяет всем условиям пункта б). | удовлетворяет всем условиям пункта б). | ||
| Это дерево (на самом деле таких деревьев 3, но для нас это не важно) будет открывать нашу серию. | Это дерево (на самом деле таких деревьев 3, но для нас это не важно) будет открывать нашу серию. | ||
| - | Положим x<sub>0</sub>=4, y<sub>0</sub> = 4, x<sub>k</sub> = y<sub>k-1</sub>, y<sub>k</sub> = 3y<sub>k-1</sub>-x<sub>k-1</sub>}-1. | + | Положим x<sub>0</sub>=4, y<sub>0</sub> = 4, x<sub>k</sub> = y<sub>k-1</sub>, y<sub>k</sub> = 3y<sub>k-1</sub>-x<sub>k-1</sub>-1. |
| Легко убедиться (по индукции), что дерево, у которого три вершины, не являющиеся висячими, имеют степени 3, | Легко убедиться (по индукции), что дерево, у которого три вершины, не являющиеся висячими, имеют степени 3, | ||
| x<sub>k</sub>, y<sub>k</sub> при любом натуральном будет удовлетворять условиям пункта б). | x<sub>k</sub>, y<sub>k</sub> при любом натуральном будет удовлетворять условиям пункта б). | ||