2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Игра с многочленами
Сообщение26.01.2012, 03:29 


11/10/08
171
Redmond WA, USA
Обозначим через $P$ наименьшее множество функций одной переменной $n$, принимающей целые положительные значения, содержащее константную функцию $1$ и замкнутое относительно возведения в степень по основанию $n$ и сложения, т.е. множество всех "многоэтажных многочленов" с целыми положительными коэффициентами, например $n^{n^{n^2}+n}+n^{2n+1}+n^3+4=n^{n^{n^{1+1}}+n^1}+n^{n^1+n^1+1}+n^{1+1+1}+1+1+1+1.$

Рассмотрим игру с одним игроком, которая происходит по следующим правилам. Первым ходом игрок выбирает по своему усмотрению любую функцию из множества $P$ (она становится текущей) и любой положительный целый аргумент. Каждым следующим ходом игрок выбирает любой положительный целый аргумент (но не меньший, чем на предыдущем ходе) и заменяет текущую функцию на любую функцию из множества $P$, имеющую меньшее значение для этого аргумента, чем текущая функция. Если игрок не может сделать ход, он проигрывает.

Верно ли, что игрок проигрывает при любой игре?

 Профиль  
                  
 
 Re: Игра с многочленами
Сообщение26.01.2012, 14:35 
Заслуженный участник


12/08/10
1608
Это задача на вполне упорядоченные множества или меня глючит и есть пример бесконечной игры?

 Профиль  
                  
 
 Re: Игра с многочленами
Сообщение26.01.2012, 20:47 


11/10/08
171
Redmond WA, USA
Если бы я сказал, то это была бы подсказка. :wink:

 Профиль  
                  
 
 Re: Игра с многочленами
Сообщение29.01.2012, 11:35 
Заслуженный участник
Аватара пользователя


03/12/11
640
Україна
Игрок проигрывает при любой игре. Заметим, что игрок не может бесконечно долго "оставаться на одном и том же аргументе", т.к. тогда значение каждой следующей функции на этом аргументе должно быть меньше предыдущего, а все эти значения - натуральные числа. Значит аргумент должен увеличиваться до бесконечности, причём на каждом аргументе происходит только конечное количество уменьшений функции. Для каждого аргумента, нас интересуют только две крайние функции - "вход" с меньшего аргумента и "выход" на больший аргумент. Т.е., не ограничивая общности, можно считать, что есть возрастающая последовательность аргументов $$a_1<a_2<a_3<\dots$$ и последовательность функций $\eta_0, \eta_1, \eta_2, \dots$ из $P$, такая, что $$\eta_0(a_1)>\eta_1(a_1), \; \eta_1(a_2)>\eta_2(a_2), \; \eta_2(a_3)>\eta_3(a_3),  \; \dots,$$ и нужно доказать, что такая последовательность не может быть бесконечной ни при какой игре игрока. Идея состоит в том, чтобы параллельно с "многочленами" $\eta_i$ рассматривать приведённые "многочлены", в которых коэффициенты всегда меньше текущего аргумента, но которые, в отличие от исходных "многочленов", будут обязательно убывать в соответствии с некоторым определённым на $P$ порядком, превращающим его во вполне упорядоченное множество. Т.к. в этой последовательности найдётся наименьший элемент, то он же будет в ней и последним, т.е. сама последовательность на нём обрывается и обязана быть конечной.

Более строго это выглядит так. Пусть $\mathbb{N}^0$ - множество неотрицательных целых чисел. Определим рекурсивно следующие множества с заданным на каждом из них линейным порядком:
1) $S_0=\{\varnothing\}$ - множество состоит из единственного элемента, являющегося пустым множеством. Будем также обозначать этот элемент знаком $\Lambda$.
2) Для любого $n \in \mathbb{N}$, если $S_i$ вместе с порядком $\prec$ определены для всех $i<n$, то определим $S_{n}$ как множество конечных упорядоченных наборов $$S_{n}=\{\gamma_1 \succcurlyeq \gamma_2 \succcurlyeq \dots \succcurlyeq \gamma_m \mid m \in \mathbb{N}^0, \; \gamma_1, \gamma_2, \dots,\gamma_m \in S_{n-1}\}.$$При этом $m=0$ соответствует пустой набор, т.е. $\Lambda$ также включается в $S_{n}$. Для любых элементов $\alpha, \beta \in S_{n}$, если $\alpha = (\gamma_1',\gamma_2',\dots,\gamma_{m'}')$, $\beta = (\gamma_1'',\gamma_2'',\dots,\gamma_{m''}'')$ и различие в этих последовательностях начинается с $i$-го элемента, то порядок между $\alpha$ и $\beta$ определяется таким же, как и между $\gamma_i'$ и $\gamma_i''$; в случае отсутствия $i$-го элемента в наборе, задающем один из элементов, он (элемент) считается меньшим. В частности, $\Lambda$ - наименьший элемент $S_{n}$. Для определённости стоит отметить, что элемент, определяемый набором из одного элемента $\gamma_1$ при $m=1$ - это не то же самое, что этот элемент сам по себе, так же, как и $\varnothing$ не то же самое, что $\{\varnothing\}$. В частности, $S_1$ можно считать по сути дела эквивалентом $\mathbb{N}^0$ и в нём, наряду с $\Lambda$, будет присутствовать также элемент $\{\Lambda\}$, соответствующий единице в $\mathbb{N}^0$.
По индукции доказывается, что:
1) $S_0 \subset S_1 \subset S_2 \subset \dots$ ;
2) Порядок на каждом следующем множестве совпадает с порядком на предыдущем;
3) Порядок на каждом множестве является полным.
После этого можно естественным образом определить упорядоченное множество $S=\bigcup\limits_{i=0}^{\infty} S_i,$ которое будет вполне упорядоченным.
Теперь каждому элементу из $S$ можно поставить в соответствие некоторую функцию $f \colon \mathbb{N} \to \mathbb{N}^0$, также рекурсивным образом:
1) Элементу $\Lambda$ из $S_0$ ставится в соответствие функция $f_{\Lambda}(x) \equiv 0$.
2) Для любого $n \in \mathbb{N}$, если каждому $\gamma \in S_{n-1}$ уже поставлена в соответствие некоторая функция $f_{\gamma}(x) \colon \mathbb{N} \to \mathbb{N}^0$, то для любого $\alpha = (\gamma_1,\gamma_2,\dots,\gamma_m) \in S_{n}$ положим $f_{\alpha}(x) \equiv \sum\limits_{i=1}^m {x^{f_{\gamma_i}(x)}}$.
По индукции доказывается, что при таком сопоставлении каждому элементу из $S_{n-1}$ в $S_{n}$ будет сопоставлена та же функция, что и в $S_{n-1}$.
Если $F_n$ - множество функций, соответствующих всем элементам из $S_n$, а $F=\bigcup\limits_{n=0}^{\infty} F_n$ - множество функций, соответствующих всем элементам из $S$, то тогда можно показать, что $F \setminus F_0$ есть множество $P$, фигурирующее в условии задачи.
Для любого натурального $m \geqslant 2$ также определим множество $S^{(m)}$ аналогично $S$, но с той разницей, что на каждом шаге в определении $S_n^{(m)}$ будем требовать, чтобы ни один элемент $\gamma \in S_{n-1}^{(m)}$ не входил в набор, задающий определяемый в $S_{n}^{(m)}$ элемент, $m$ (или больше) раз. Очевидно, $S^{(2)} \subset S^{(3)} \subset S^{(4)} \subset \dots$ и $S=\bigcup\limits_{m=2}^{\infty} S^{(m)}$.
Можно определить операцию "увеличения на единицу" $+1 \colon S \to S$ так: если $\alpha \in S_n$, $n \geqslant 1$, то $\alpha + 1$ определяется как набор (опять же из $S_n$), задаваемый дописыванием $\Lambda$ справа к набору, определяющему $\alpha$. Очевидно, тогда для любого $\alpha \in S$ и для любого натурального $m$: $f_{\alpha+1}(m)=f_{\alpha}(m)+1$. Кроме этого, приведением к общему шагу определения $S_n$ легко доказать, что $\beta \succ \alpha \Rightarrow \beta \succcurlyeq \alpha +1$.

Утверждение 1. Если $\alpha, \beta \in S^{(m)}$, $m \geqslant 2$ и $\alpha \prec \beta$, то $f_{\alpha}(m) < f_{\beta}(m)$.
Можно доказать индукцией по шагу построения $n$ при каждом фиксированном $m$, с использованием вышеуказанных свойств "прибавления единицы" и определения функции $f$, постепенно производя свёртку "хвоста" последовательности, задающей $\alpha$, начиная с самого меньшего элемента.

Утверждение 2. Если $m \geqslant 3$, то для любого $\alpha \in S \setminus S^{(m)}$ существует такой элемент $\alpha_1 \in S$, что:
а) $f_{\alpha_1}(2) < f_{\alpha}(2)$ ;
б) $f_{\alpha_1}(m) = f_{\alpha}(m)$ ;
в) $f_{\alpha_1}(t) > f_{\alpha}(t)$ при всех $t>m$.

Доказывается также индукцией по шагу построения $n$ при каждом фиксированном $m$. Если $\alpha =(\gamma_1',\gamma_2',\dots,\gamma_{m'}')$, то либо какой-то элемент $\gamma_i$ не принадлежит $S^{(m)}$ и мы заменяем его на $\alpha_1'$, найденный для $\gamma_i$ и существующий в силу индуктивного предположения, либо какой-то элемент $\gamma_i$ встречается в последовательности (минимум) $m$ раз и тогда мы выбрасываем эту группу из $m$ элементов (оставляя остальные вхождения $\gamma_i$, если они есть) и заменяем её на единственный элемент $\gamma_i+1$. Полученный ряд, упорядоченный соответствующим образом, и определит $\alpha_1$. При определении $\alpha_1$, возможно, придётся повысить шаг $n$, но это не нарушит логики индукции, ибо мы использовали доказываемое утверждение только для $\gamma_i$ (и то только в первом случае).

Взяв какой-либо исходный элемент $\alpha \notin S^{(m)}$ и многократно применяя утверждение 2, получим некоторую последовательность $\alpha_0 = \alpha, \alpha_1, \alpha_2, \dots$ элементов $S$, такую, что для любого $i \geqslant 0$
а) $f_{\alpha_{i+1}}(2) < f_{\alpha_{i}}(2)$ ;
б) $f_{\alpha_{i+1}}(m) = f_{\alpha_{i}}(m)$ ;
в) $f_{\alpha_{i+1}}(t) > f_{\alpha_{i}}(t)$ при всех $t>m$.
В силу свойства a), эта последовательность не может быть бесконечной и мы рано или поздно придём к элементу из $S^{(m)}$. Поэтому, в силу свойств б) и в), верно
Утверждение 3. Если $m \geqslant 3$, $\alpha \in S \setminus S^{(m)}$, то найдётся такой элемент $\beta \in S^{(m)}$, что:
а) $f_{\alpha}(m) = f_{\beta}(m)$ ;
б) $f_{\alpha}(t) < f_{\beta}(t)$ при всех $t>m$.


Возвращаясь к задаче, будем считать, не ограничивая общности, что $a_1 \geqslant 3$. По каждой функции $\eta_i(x)$, $i \geqslant 1$, построим элемент $\tau_i \in S^{(a_i)}$ вместе с соответствующей функцией $\eta_{\tau_i}(x)$, следующим образом. Как было сказано выше, $\eta_i(x) \in F \setminus F_0$, поэтому $\eta_i(x) \equiv f_{\alpha}(x)$ для некоторого $\alpha \in S$. Если $\alpha \in S^{(a_i)}$, то полагаем $\tau_i=\alpha$, иначе используем утверждение 3 и положим $\tau_i=\beta$, найденному из этого утверждения. В любом случае, $\eta_i(a_i)=f_{\tau_i}(a_i)$, а $\eta_i(a_{i+1}) \leqslant f_{\tau_i}(a_{i+1})$. Учитывая, что $\eta_i(a_{i+1})>\eta_{i+1}(a_{i+1})=f_{\tau_{i+1}}(a_{i+1})$, при любом $i \geqslant 1$ получим:$$f_{\tau_i}(a_{i+1}) > f_{\tau_{i+1}}(a_{i+1}) \eqno(*)$$ Но $\tau_i \in S^{(a_i)} \subset S^{(a_{i+1})}$ и $\tau_{i+1} \in S^{(a_{i+1})}$, поэтому из $(*)$ и из утверждения 1 получаем, что $\tau_i \succ \tau_{i+1}$. Значит последовательность $\{\tau_i\}$ - убывающая во вполне упорядоченном множестве $S$ а, стало быть, конечна. $\blacksquare$

Доказанное утверждение есть обобщение теоремы Гудстейна, которую, как известно, невозможно доказать, исходя только из аксиом Пеано. "Игра", которая фигурирует в теореме Гудстейна, ограничена тем, что там обязано чередоваться увеличение аргумента ровно на единицу с уменьшением значения функции тоже ровно на единицу, причём коэффициенты у всех частей вновь выбираемой функции должны быть меньше текущего аргумента, т.е. там "игра" по сути дела детерминирована и состоит только из выбора начального значения. Здесь же, благодаря автору задачи, появилось некоторое разнообразие.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group