Откуда задача не знаю. Воспроизвожу по памяти.
Ha одном острове в океане у народа была писменность. Очень странная.
Алфавит состоял всего из трех букв (abc). Причем если в слове подряд дважды идет одинаковая последовательность символов, то такое слово считается неправильным.
Пример №1
a ab abacab правильные слова
aa cababc неправильные слова
Пример №2 если алфавит состоит из двух букв, то количество правильных слов конечно:
a b ab ba aba bab
Доказать, что можно составить бесконечное количество правильных слов при алфавите состоящем из трех букв.
Тарабарский язык
Тарабарский язык
Последний раз редактировалось Pavlovsky 30 ноя 2019, 11:13, всего редактировалось 1 раз.
Причина: test
Причина: test
Тарабарский язык
Pavlovsky писал(а):Source of the post
Откуда задача не знаю. Воспроизвожу по памяти.
Ha одном острове в океане у народа была писменность. Очень странная.
Алфавит состоял всего из трех букв (abc). Причем если в слове подряд дважды идет одинаковая последовательность символов, то такое слово считается неправильным.
Пример №1
a ab abacab правильные слова
aa cababc неправильные слова
Пример №2 если алфавит состоит из двух букв, то количество правильных слов конечно:
a b ab ba aba bab
Доказать, что можно составить бесконечное количество правильных слов при алфавите состоящем из трех букв.
Одна из древних МГУшных олимпиад по математике и структурной лингвистике
Идея решения, как я предполагаю, состоит в нахождении закона порождения слова из слова подстановкой типа (a)=(ac), и доказательства бесконечности такого процесса.
Последний раз редактировалось Natrix 30 ноя 2019, 11:13, всего редактировалось 1 раз.
Причина: test
Причина: test
Тарабарский язык
Одна из древних МГУшных олимпиад по математике и структурной лингвистике
Нифига себе в МГУ задачи задают. Когда мне эта задача (года три назад) попалась на глаза, я ee решал 2 (Две) недели!
Последний раз редактировалось Pavlovsky 30 ноя 2019, 11:13, всего редактировалось 1 раз.
Причина: test
Причина: test
Тарабарский язык
Pavlovsky писал(а):Source of the postОдна из древних МГУшных олимпиад по математике и структурной лингвистике
Нифига себе в МГУ задачи задают. Когда мне эта задача (года три назад) попалась на глаза, я ee решал 2 (Две) недели!
Это задачка для абитуры!!! Победителей этой олимпиады брали на "Структурную лингвистику" без экзаменов
Последний раз редактировалось Natrix 30 ноя 2019, 11:13, всего редактировалось 1 раз.
Причина: test
Причина: test
Тарабарский язык
Излагаю свое доказательство:
Будем строить бесконечную последовательность правильных слов. Пусть у нас есть тройка слов
, такая что если в правильном слове X, заменить , то получится тоже правильное слово X’.
Пусть тройка M удовлетворяет свойствам:
1. .
2. Любая комбинация, состоящая из одного, двух (различных) и трех (среднее слово не равно крайним) слов из M есть:
2.1. Правильные слова
2.2. Слово A в них встречается только в начале слов и больше нигде.
Теорема:
Пусть тройка слов M удовлетворяет вышеприведенным свойствам. Тогда если в правильном слове X, заменить , то получится тоже правильное слово X’.
Доказательство:
1. Предположим, что X’ неправильное слово. Тогда в нем должна содержаться последовательность вида .
2. Если начинается c или или . Тогда и состоят целиком из последовательности одинаковых слов из M (это следует из свойств 1 и 2 тройки M). Ho это невозможно, так как тогда , что противоречит утверждению, что X правильное слово.
3. Итак начинается где то c середины некоторого слова из M. Пусть , где хвостик слова из M; начало слова из M; состоит из целых слов из M либо пусто.
4. Тогда .
5. Легко убедиться, что . Состоят из одинаковой последовательности слов из M.
6. Тогда получается слово из M.
7. Ho в этом случае у нас в X’ есть последовательность . Причем в последовательности есть две подряд идущие одинаковые последовательности и , что противоречит свойству 2.1 тройки M.
8. Вывод. Гипотеза, что X’ неправильное слово неверна. Значит X’ правильное слово.
Осталось только найти тройку M удовлетворяющую условиям теоремы.
Попробуйте сделать это самостоятельно.
PS Поступление в МГУ обещать не могу, но плюсики поставить могу:
1. Тому, кто первым представит тройку M удовлетворяющую условиям теоремы.
2. Тому, чья суммарная длина тройки M будет минимальной.
3. Тому, чья суммарная длина тройки M будет меньше моей (у меня получилось 40 символов в трех словах).
4. Тому, кто предложит доказательство отличное от моего.
Будем строить бесконечную последовательность правильных слов. Пусть у нас есть тройка слов
, такая что если в правильном слове X, заменить , то получится тоже правильное слово X’.
Пусть тройка M удовлетворяет свойствам:
1. .
2. Любая комбинация, состоящая из одного, двух (различных) и трех (среднее слово не равно крайним) слов из M есть:
2.1. Правильные слова
2.2. Слово A в них встречается только в начале слов и больше нигде.
Теорема:
Пусть тройка слов M удовлетворяет вышеприведенным свойствам. Тогда если в правильном слове X, заменить , то получится тоже правильное слово X’.
Доказательство:
1. Предположим, что X’ неправильное слово. Тогда в нем должна содержаться последовательность вида .
2. Если начинается c или или . Тогда и состоят целиком из последовательности одинаковых слов из M (это следует из свойств 1 и 2 тройки M). Ho это невозможно, так как тогда , что противоречит утверждению, что X правильное слово.
3. Итак начинается где то c середины некоторого слова из M. Пусть , где хвостик слова из M; начало слова из M; состоит из целых слов из M либо пусто.
4. Тогда .
5. Легко убедиться, что . Состоят из одинаковой последовательности слов из M.
6. Тогда получается слово из M.
7. Ho в этом случае у нас в X’ есть последовательность . Причем в последовательности есть две подряд идущие одинаковые последовательности и , что противоречит свойству 2.1 тройки M.
8. Вывод. Гипотеза, что X’ неправильное слово неверна. Значит X’ правильное слово.
Осталось только найти тройку M удовлетворяющую условиям теоремы.
Попробуйте сделать это самостоятельно.
PS Поступление в МГУ обещать не могу, но плюсики поставить могу:
1. Тому, кто первым представит тройку M удовлетворяющую условиям теоремы.
2. Тому, чья суммарная длина тройки M будет минимальной.
3. Тому, чья суммарная длина тройки M будет меньше моей (у меня получилось 40 символов в трех словах).
4. Тому, кто предложит доказательство отличное от моего.
Последний раз редактировалось Pavlovsky 30 ноя 2019, 11:13, всего редактировалось 1 раз.
Причина: test
Причина: test
Тарабарский язык
я помню у меня такая задача была в книжке занимательные задачи по математике, которую мне подарили на выпуске из детского сада....))
Последний раз редактировалось Pavlukhin 30 ноя 2019, 11:13, всего редактировалось 1 раз.
Причина: test
Причина: test
Тарабарский язык
Слова удовлетворяющие условиям теоремы.
abcabac
abcacbacabacb
abcacbacabcbacbcabcb
abcabac
abcacbacabacb
abcacbacabcbacbcabcb
Последний раз редактировалось Pavlovsky 30 ноя 2019, 11:13, всего редактировалось 1 раз.
Причина: test
Причина: test
Тарабарский язык
Вернусь к этой задаче еще раз. Эта задача может быть сформулирована немного иначе.
Постановка задачи вариант №2
Ha одном oстрове в океане у народа была писменность. Очень странная.
Алфавит coстоял всего из трех букв (abc). Причем eсли в слове подряд дважды идет одинаковая последовательность символов, то такое слово считается эквивалентным (одинаковым по смыслу) co словом полученным из текущего удалением одной из одинаковых последовательностей.
Вопрос: в этом языке конечное или бесконечное число смыслов слов (не эквивалентных слов)?
Эта задача отличается от варианта №1. Так как два несократимых слова могут быть эквивалентными по смыслу: abc=a(bc)(bc)=(abcb)(abcb)c=abcba(bc)(bc)=abcbabc.
Постановка задачи вариант №2
Ha одном oстрове в океане у народа была писменность. Очень странная.
Алфавит coстоял всего из трех букв (abc). Причем eсли в слове подряд дважды идет одинаковая последовательность символов, то такое слово считается эквивалентным (одинаковым по смыслу) co словом полученным из текущего удалением одной из одинаковых последовательностей.
Вопрос: в этом языке конечное или бесконечное число смыслов слов (не эквивалентных слов)?
Эта задача отличается от варианта №1. Так как два несократимых слова могут быть эквивалентными по смыслу: abc=a(bc)(bc)=(abcb)(abcb)c=abcba(bc)(bc)=abcbabc.
Последний раз редактировалось Pavlovsky 30 ноя 2019, 11:13, всего редактировалось 1 раз.
Причина: test
Причина: test
Вернуться в «Дискретная математика»
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 72 гостей