Тарабарский язык

Pavlovsky · Сообщение **Pavlovsky** » 24 май 2007, 16:04

Откуда задача не знаю. Воспроизвожу по памяти.
Ha одном острове в океане у народа была писменность. Очень странная.
Алфавит состоял всего из трех букв (abc). Причем если в слове подряд дважды идет одинаковая последовательность символов, то такое слово считается неправильным.

Пример №1
a ab abacab правильные слова
aa cababc неправильные слова
Пример №2 если алфавит состоит из двух букв, то количество правильных слов конечно:
a b ab ba aba bab

Доказать, что можно составить бесконечное количество правильных слов при алфавите состоящем из трех букв.

Natrix · Сообщение **Natrix** » 24 май 2007, 22:41

Pavlovsky писал(а):Source of the post
Откуда задача не знаю. Воспроизвожу по памяти.
Ha одном острове в океане у народа была писменность. Очень странная.
Алфавит состоял всего из трех букв (abc). Причем если в слове подряд дважды идет одинаковая последовательность символов, то такое слово считается неправильным.

Пример №1
a ab abacab правильные слова
aa cababc неправильные слова
Пример №2 если алфавит состоит из двух букв, то количество правильных слов конечно:
a b ab ba aba bab

Доказать, что можно составить бесконечное количество правильных слов при алфавите состоящем из трех букв.

Одна из древних МГУшных олимпиад по математике и структурной лингвистике
Идея решения, как я предполагаю, состоит в нахождении закона порождения слова из слова подстановкой типа (a)=(ac), и доказательства бесконечности такого процесса.

Pavlovsky · Сообщение **Pavlovsky** » 25 май 2007, 11:35

Одна из древних МГУшных олимпиад по математике и структурной лингвистике

Нифига себе в МГУ задачи задают. Когда мне эта задача (года три назад) попалась на глаза, я ee решал 2 (Две) недели!

Natrix · Сообщение **Natrix** » 25 май 2007, 20:18

Pavlovsky писал(а):Source of the post
Одна из древних МГУшных олимпиад по математике и структурной лингвистике

Нифига себе в МГУ задачи задают. Когда мне эта задача (года три назад) попалась на глаза, я ee решал 2 (Две) недели!

Это задачка для абитуры!!! Победителей этой олимпиады брали на "Структурную лингвистику" без экзаменов

Pavlovsky · Сообщение **Pavlovsky** » 28 май 2007, 14:37

Излагаю свое доказательство:
Будем строить бесконечную последовательность правильных слов. Пусть у нас есть тройка слов
$$M=(M_1,M_2,M_3)$$

, такая что если в правильном слове X, заменить $a \to M_1, b \to M_2, c \to M_3$ , то получится тоже правильное слово X’.

Пусть тройка M удовлетворяет свойствам:
1. $M_1=AB, M_2=AC, M_3=AD. B \ne C, B \ne D, C \ne D$ .
2. Любая комбинация, состоящая из одного, двух (различных) и трех (среднее слово не равно крайним) слов из M есть:
2.1. Правильные слова
2.2. Слово A в них встречается только в начале слов $$M_1,M_2,M_3$$

и больше нигде.

Теорема:
Пусть тройка слов M удовлетворяет вышеприведенным свойствам. Тогда если в правильном слове X, заменить $a \to M_1, b \to M_2, c \to M_3$ , то получится тоже правильное слово X’.
Доказательство:
1. Предположим, что X’ неправильное слово. Тогда в нем должна содержаться последовательность вида $$E'_1E'_2. E'_1=E'_2$$

.
2. Если $$E'_1$$

начинается c $$M_1$$

или

. Тогда

и

состоят целиком из последовательности одинаковых слов из M (это следует из свойств 1 и 2 тройки M). Ho это невозможно, так как тогда $$E_1=E_2$$

, что противоречит утверждению, что X правильное слово.
3. Итак $$E'_1$$

начинается где то c середины некоторого слова из M. Пусть $$E'_1=K'_1F'_1H'_1$$

, где

хвостик слова из M; $$H'_1$$

начало слова из M; $$F'_1$$

состоит из целых слов из M либо пусто.
4. Тогда $$E'_2=K'_2F'_2H'_2$$

.
5. Легко убедиться, что $$F'_1= F'_2$$

. Состоят из одинаковой последовательности слов из M.
6. Тогда получается $$K'_1= K'_2; H'_1= H'_2; H'_1K'_2$$

слово из M.
7. Ho в этом случае у нас в X’ есть последовательность $$M_iFM_jFM_l$$

. Причем в последовательности $$M_iM_jM_l$$

есть две подряд идущие одинаковые последовательности $$K'_1H'_1$$

и

, что противоречит свойству 2.1 тройки M.
8. Вывод. Гипотеза, что X’ неправильное слово неверна. Значит X’ правильное слово.

Осталось только найти тройку M удовлетворяющую условиям теоремы.
Попробуйте сделать это самостоятельно.

PS Поступление в МГУ обещать не могу, но плюсики поставить могу:
1. Тому, кто первым представит тройку M удовлетворяющую условиям теоремы.
2. Тому, чья суммарная длина тройки M будет минимальной.
3. Тому, чья суммарная длина тройки M будет меньше моей (у меня получилось 40 символов в трех словах).
4. Тому, кто предложит доказательство отличное от моего.

Pavlukhin · Сообщение **Pavlukhin** » 28 май 2007, 19:26

я помню у меня такая задача была в книжке занимательные задачи по математике, которую мне подарили на выпуске из детского сада....))

Pavlovsky · Сообщение **Pavlovsky** » 01 июн 2007, 11:40

Слова удовлетворяющие условиям теоремы.
abcabac
abcacbacabacb
abcacbacabcbacbcabcb

Pavlovsky · Сообщение **Pavlovsky** » 15 дек 2008, 09:04

Вернусь к этой задаче еще раз. Эта задача может быть сформулирована немного иначе.

Постановка задачи вариант №2

Ha одном oстрове в океане у народа была писменность. Очень странная.
Алфавит coстоял всего из трех букв (abc). Причем eсли в слове подряд дважды идет одинаковая последовательность символов, то такое слово считается эквивалентным (одинаковым по смыслу) co словом полученным из текущего удалением одной из одинаковых последовательностей.

Вопрос: в этом языке конечное или бесконечное число смыслов слов (не эквивалентных слов)?

Эта задача отличается от варианта №1. Так как два несократимых слова могут быть эквивалентными по смыслу: abc=a(bc)(bc)=(abcb)(abcb)c=abcba(bc)(bc)=abcbabc.

yourdomain.com