Пусть T -- дерево с корнем, в котором бесконечное число вершин. Пусть известно, что степень каждой вершины конечна. Докажите, что есть бесконечный путь, который начинается в корне.
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
14:02:29
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
14:02:29
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.11.2024 03:32:31 (i2).
Десктопная версия, переключиться на мобильную.
При поддержке
блин, теперь я не понял :(
вот пусть A(n) - множество путей длины n, выходящих из корня; множество A(n+1) может либо уменьшаться по сравнению с A(n) (если есть некоторая вершина, находящаяся на расстоянии n от корня, и её степень равна 1), либо увеличиваться (если есть некоторая вершина, находящаяся на расстоянии n от корня, и её степень больше двух)
очевидно, что если множество A(n) - пустое, то A(n+1) тоже пустое
если на некотором бесконечно большом шаге множество A(n) стало пустым, то это значит, что все вершины находятся на меньшем расстоянии от корня, чем n, т.е. количество таких вершин конечно и меньше n2, что противоречит условию задачи
значит, для любого бесконечно большого n существует такое k, что k>n и мощность множества A(k) будет больше нуля
В дереве n-1 ребер. Т.к. n = бесконечности, то число ребер m бесконечно. А так как число ребер m - бесконечно, то есть и бесконечный путь :)
Докажите, что найдется такое бесконечное слово в алфавите Σ, что
сколь угодно длинное его начало является началом какого-нибудь слова из
A.
Объясните пожалуйста, в чем разница между разными путями, и одним?
ilyaraz сказал: "Могут быть сколь угодно длинные пути, но все конечные."
Если мы доказали что для любого n существует путь длны больше n, разве это не доказывает существования сколь угодно длинного (бесконечного) пути? (Заметим, что числа натуральные).
"Да, для каждого n найдется путь длиннее n. Но это могут быть разные пути. Нам же нужно доказать существование одного пути, длина которого бесконечна, то есть длиннее любого n."
что в том, что пути разные ?
у нас есть бесконечная последовательность натуральных чисел, она состоит из конечных чисел, но ограничения сверху её нет. Ясно, что все числа конечны.
с путями такая же ситауция да?
не вижу в чем принципиальность продолжения предыщего.
http://codeforces.net/comments/146#comment-1668
у нас есть путь A длины n рёбер.
и путь B длины n + k рёбер, пусть C путь длины n такой что первые его n рёбер совпадают с первыми рёбрами пути B (C префикс B).
вам очень важно, чтобы A было равно C? вернёмся к первому утверждению и заменим букву A на букву C.
какая разница какой из путей длины n взять в качестве старта ? A или С, или у пути B может не быть "предпути" (префикса) ?
http://codeforces.net/comments/146#comment-1688
Смотрите: если есть сколь угодно длинные никак не связанные друг с другом пути, то бесконечного пути запросто может не оказаться, пример здесь приводился. Если же нам известно, что они являются один началом другого, то наступает счастье - возьмём пути p_i (длина p_i равна i, p_i - начало p_{i+1}). Тогда каждый следующий путь отличается от предыдущего на один элемент a_i, и мы можем построить искомый путь p_1 a_2 a_3 a_4 ... - он уже бесконечен.
Вообще когда я решал эту задачу, я пришёл к идее предложенной
it4.kp, но понял что это неверно в случае, степень вершины может быть бесконечной, и мне пришлось вернуться на страницу чтобы свериться с формулировкой задачи, и убедиться в правильном понимании условия. В противном случае, решения бы небыло.
А вот утверждение сделаное ilyaraz, я считаю неверным.
Мда, не работать мне в 5 классе.
Спор не спор, речь не об этом. Речь об использованном вами приёме.
Почему определять удобно именно так: обычно от бесконечного объекта нужно, чтобы его конечные части были как-то согласованы.
Наивный мотивирующий пример. Бредовый, конечно, но, может быть, зато понятный?.. :)
Рассмотрим все целые неотрицательные степени двойки. Запишем их в десятичной системе счисления: 1, 2, 4, 8, 16, 32, 64, 128, ... . Можно было бы сказать, что предел этих записей - бесконечная степень двойки. Но ничего полезного с ней сделать не получится: мы не знаем ни одной цифры этого объекта, ни первой, ни последней, вообще никакой.
С другой стороны, рассмотрим все степени десятки. Их записи в десятичной системе счисления выглядят так: 1, 10, 100, ... . Если мы скажем, что предел этих записей - бесконечная степень десятки, от этого будет хотя бы та польза, что мы знаем, как этот предел выглядит: 10000000... .
Разница в том, что здесь запись степени десятки содержит в качестве префиксов все записи конечных степеней. Из-за этого легко по индукции доказать, что предел будет именно таким.
Итак, я уже не пытаюсь сказать что ilyaraz был не прав, он был прав. Но всё же есть тут что-то "парадоксальное".
Gassa: "Определение: бесконечный путь - это предел конечных путей возрастающей длины, каждый следующий из которых содержит предыдущий как префикс."
1) предположим, что мы доказали что для любого пути A есть более длинный путь B такой что A его префикс.
2) предположим что мы доказали что для любого пути A есть другой более длинный путь B
3) 1-ое означает что у нас есть бесконечный путь. 2-ое нет, хотя ни у кого не вызывает сомнений, что у B есть префикс длины |A|
Я не сомневаюсь в справедливости 3-его, но точно всё осмыслить понять почему так не удалось.
По моему из этого пункта следует только то, что у нас есть бесконечное множество путей, среди которых мы не сможем выделить максимальный по длине, но тем не менее, среди них может вообще не оказаться бесконечного пути, то есть все они могут быть конечны.
Более того мне кажется, что бесконечного пути по таким условиям быть вообще не может, ибо не понятно, как бесконечный по длине путь может быть префиксом другого пути?
Назовем фильтром множество подмножеств натуральных чисел, удовлетворяющее четырем условиям:
1. Фильтр не пуст.
2. Пустое множество не принадлежит фильтру.
3. Если два множества принадлежат фильтру, то и их пересечение принадлежит фильтру.
4. Если множество принадлежит фильтру, то любое его надмножество также принадлежит фильтру.
Будем называть фильтр неинтересным, если найдется натуральное число, принадлежащее всем множествам в фильтре.
Задача: построить какой-нибудь пример интересного (то есть не неинтересного) фильтра.
>> 3. Если два множества принадлежат фильтру, то и их пересечение принадлежит фильтру.
А если их пересечение пусто?
А вообще - построен ли хоть один конкретный пример неглавного ультрафильтра? Или это все еще открытая проблема?
Но я в этом ничего не понимаю. Так что лучше посмотрите релевантную литературу.
Поэтому давайте вернемся с небес на землю (то есть к основной тематике сайта). Я попробую привести пример применения абстрактной теории множеств в промышленном программировании.
Предположим, что вы сидите на рабочем месте и вы голодны. Оглядевшись, вы замечаете n коллег, причем i-й коллега имеет на столе непустое множество печенек Ki. В этом случае следующая фраза не будет звучать неуместно: "Друзья, можно я воспользуюсь аксиомой выбора и возьму у каждого из вас по одной печеньке?"