2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Крестики-нолики на бесконечной клетчатой бумаге
Сообщение23.04.2019, 01:11 


17/04/19
2
Задача 30 из брошюрки Шеня «Игры и стратегии с точки зрения математики»:
Цитата:
Двое игроков ставят крестики и нолики на бесконечной клетчатой бумаге, причём на каждый крестик первого игрока второй отвечает $100$ ноликами. Докажите, что первый может добиться, чтобы некоторые четыре крестика образовали квадрат (со сторонами, параллельными линиям клеток).
Ясно, что число $100$ можно заменить на $n$, и оно никакой особой роли не играет.
Я пыталась решить задачу разными способами, все они опирались на принцип Дирихле. Неплохо бы было научиться делать «арифметические прогрессии из крестиков», то есть произвольно много крестиков, находящихся на одной линии и располагающихся через фиксированное количество клеток. Но даже этого пока не выходит. Была мысль делить линию на прямоугольники $1\times101$, или всю плоскость на квадраты, как-то применять индукцию, но все это было бесполезно. Ещё я пыталась использовать идею решения одной похожей задачи:
Цитата:
Плоскость раскрашена в 100 цветов. Докажите, что найдется прямоугольник с вершинами одного цвета.
Но она в разы проще, и даже если бы была возможность строить арифметические прогрессии произвольной длины, не получается свести эту задачу к ней. (Хотя если континуальную плоскость заменить на счетную клетчатую бумагу, то решение там не изменится).

 Профиль  
                  
 
 Re: Крестики-нолики на бесконечной клетчатой бумаге
Сообщение23.04.2019, 10:00 
Заслуженный участник
Аватара пользователя


01/08/06
3049
Уфа
А такое усиление решать умеете:
Цитата:
Плоскость раскрашена в ??? цветов. Докажите, что найдется квадрат с вершинами одного цвета.
:?:

-- Вт апр 23, 2019 12:17:10 --

Хотя нет, пожалуй, это слишком сложный путь...

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

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



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

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


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

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