$%A$% и $%B$% играют в такую игру.

$%A$% выбирает $%m$% точек на промежутке $%(0;\infty) $%.

$%B$% произвольно раскрашивает каждую из них одним из $%k$% цветов: $%C_0,C_1,…,C_{k-1}$%.

После этого $%A$% выбирает положительное число $%a$% и раскрашивает все промежутки $%\left((nk-k)a;(nk-k+1)a\right),n\in N$% в $%C_0$% цвет, все промежутки $%\left((nk-k+1)a;(nk-k+2)a\right),n\in N$% - в $%C_1$% цвет, …, а все промежутки $%\left((nk-1)a;nka\right),n\in N$%, - в $%C_{k-1}$% цвет.

Если каждая из выбранных в начале игры $%A$% точек принадлежит интервалу такого же цвета, то $%A$% считается победителем. Иначе победителем будет $%B$%. Сможет ли кто-либо из игроков обеспечить себе победу?

задан 8 Ноя '16 13:55

изменен 14 Ноя '16 12:27

10|600 символов нужно символов осталось
1

$%A$% всегда может обеспечить себе победу, выбрав точки $$x_1=k^0,x_2=k^1,...,x_m=k^{m-1}.$$ Пускай $%y_i$% - номер цвета (от $%0$% до $%k-1$%), в который $%B$% раскрасил точку $%x_i$% $%(i=1,…m)$%.

$%A$% необходимо и достаточно выбрать число $%a$% таким образом, чтобы для всех $%i=1,…m$% $$\left[\frac{x_i}a\right]\equiv y_i({\bmod \,k})\text{ и }\left\{\frac{x_i}a\right\}\ne0.$$ Для этого рассмотрим три возможных случая:

І) если все точки цвета $%A_0$% ($%y_1=y_2=...=y_m=0$%), то $%A$% выбирает $%a=k^m$% и имеем $%\left[\frac{x_i}a\right]=\left[\frac{k^{i-1}}{k^m}\right]=\left[\frac1{k^{m-i+1}}\right]=0=y_i({\bmod \,k})$% и $%\left\{\frac{x_i}a\right\}=\left\{\frac1{k^{m-i+1}} \right\}\ne0$%;

ІІ) если все точки цвета $%A_{k-1}$% ($%y_1=y_2=...=y_m=k–1$%), то $%A$% выбирает $%a=\frac{k^m}{k^{m+1}-1}$% и имеем $%\left[\frac{x_i}a\right]=\left[\frac{(k^{m+1}-1)k^{i-1}}{k^m}\right]=\left[k^i-\frac1{k^{m-i+1}}\right]=k^i+\left[-\frac1{k^{m-i+1}}\right]=k^i-1\equiv k-1=y_i({\bmod \,k} )$% и $%\left\{\frac{x_i}a\right\}=\left\{-\frac1{k^{m-i+1}}\right\}\ne0$%;

ІІІ) во всех остальных случаях $%A$% выбирает $%a=\frac{k^m-1}{k(y_1\cdot k^{m-1}+y_2\cdot k^{m-2}+...+y_m\cdot k^0)}$% и имеем $$\frac{x_i}a=\frac{(y_1\cdot k^m+y_2\cdot k^{m-1}+...+y_m\cdot k^1)k^{i-1}}{k^m-1}=$$ $$=y_1\cdot k^{i-1}+y_2\cdot k^{i-2}+...+y_{i-1}\cdot k^1+y_i\cdot k^0+$$ $$+\frac{(y_1\cdot k^{i-1}+y_2\cdot k^{i-2}+...+y_{i-1}\cdot k^1+y_i\cdot k^0)+(y_{i+1}\cdot k^{m-1}+...+y_m\cdot k^i)}{k^m-1}.$$ Поскольку все $%y_i$% не могут быть одновременно равны $%0$% и не могут быть одновременно равны $%k-1$%, то $$0<\frac{(y_1\cdot k^{i-1}+y_2\cdot k^{i-2}+...+y_{i-1}\cdot k^1+y_i\cdot k^0)+(y_{i+1}\cdot k^{m-1}+...+y_n\cdot k^i)}{k^m-1}<$$ $$<\frac{(k-1)(k^{i-1}+k^{i-2}+...+k^1+k^0)+(k-1)(k^{m-1}+...+k^i)}{k^m-1} = 1,$$ отсюда $%\left[\frac{{x_i}}a\right]=y_1\cdot k^{i-1}+y_2\cdot k^{i-2}+...+y_{i-1}\cdot k^1+y_i\cdot k^0\equiv y_i({\bmod \,k})$% и $%\left\{\frac{x_i}a\right\}\ne0$%.

ссылка

отвечен 14 Ноя '16 0:26

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×73
×52
×33

задан
8 Ноя '16 13:55

показан
861 раз

обновлен
14 Ноя '16 12:27

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru