Два игрока по очереди ставят точки в клетки таблицы $%7\times 7$%. За один ход ставится ровно одна точка. В одну клетку может быть поставлено несколько точек (ставить точки на границы клеток нельзя). Проигрывает тот, после чьего хода в клетках какой-то строки или столбца суммарно будут стоять 5 точек. Кто из игроков может обеспечить себе победу независимо от игры соперника?

(Минская городская олимпиада)

............................................................

Меня смущает, что в одну клетку может быть поставлено несколько точек, ведь добавление данной детали в условие задачи лишь облегчает её решение! Действительно, вторму игроку для победы достаточно в ответ на ход первого игрока ставить точку в той же самой клетке, что и первый. Изначально таблица пуста (во всяком случае, в условии не указано, что это не так), следовательно, в каждом строке и в каждой столбце чётное число точек. Ход первого игрока нарушает условие чётности (ровно в одной строке и ровно в одном столбце теперь нечётное число точек), а ответный ход второго возвращает всё на круги своя - и снова в каждой строке и в каждом столбце чётное число. Следовательно, первый игрок рано или поздно проиграет. Разве не так?

А если изменить условие и запретить ставить в одну клетку более одной точки, что тогда? Пожалуйста, помогите решить. Заранее благодарю!

задан 12 Дек '17 2:58

изменен 12 Дек '17 2:59

1

@Аллочка Шакед: может быть, потому и добавили, что в противном случае получается сложная задача? С ходу непонятно, к то выиграет, и какова стратегия. Я пробовал применять какие-то соображения, но общей картины пока не складывается. Хотя условие звучит весьма естественно и интересно.

(12 Дек '17 11:11) falcao

@falcao, мне конопляжется, что второй игрок в ответ на каждый ход первого должен ставить точку в той же строке, что и первый, но в том столбце, в котором менее 4 точек. Тогда количество точек в каждой строке после хода второго будет чётным, а столбец с менее 4 точками для второго игрока всегда найдётся, так как если после хода первого игрока в одном из столбцов будет 5, то первый уже проиграл, а ровно по 4 в каждом столбце после хода первого игрока быть не может, так как 7*4=28 чётное число, а после хода первого игрока общее число точек нечётно.

НУ И ГДЕ У МЕНЯ ОШИБКА???

(12 Дек '17 12:06) Аллочка Шакед
1

@Аллочка Шакед: попытки сформулировать стратегии такого типа у меня были, но ни к чему не привели. То, что Вы описали, по-моему, не достаточно. Почему не может так оказаться, что у второго игрока не найдётся хода? Он должен ставить точку в клетке определённой i-й строки, где какие-то поля свободны. Общее число сделанных ходов в этот момент нечётно. Но почему не может оказаться, что во всех столбцах, для которых клетки i-й строки свободны, имеется ровно по 4 клетки? Ведь отсюда следует чётность только по этим столбцам, а не по всей таблице.

(12 Дек '17 12:26) falcao
1

При числе точек меньше 28 всегда найдется строка, куда можно поставить точку, ... и столбец, конечно, тоже. Можно разрешить первому поставить сразу 14 точек. От этого результат не изменится. Мне подсказали контрпример с квадратами 4х4 и 3х3. Этот комментарий не удаляю,... становится интересно.

(12 Дек '17 14:09) Urt
1

@Urt: понятно, что при количестве меньше 28 найдётся "хорошая" строка, а также "хороший" столбец. Но у меня это рассуждение ещё вчера "упёрлось" в то, что на их пересечении место уже может оказаться занято. Можно ли преодолеть эту трудность?

Случай 3x3 я прослеживал, а 4x4 не смотрел. Контрпримеры к какому утверждению Вы имели в виду?

(12 Дек '17 17:44) falcao

@falcao, контрпример к неподкрепленному другими посылками заключению о том, что при наличии хорошей строки и хорошего столбца найдется и хорошая клетка. Задачку увидел сегодня - решил сделать небольшой (так, на 5-10 мин.) перерыв и отвлечься от дел..., но этот процесс затягивается. Задача интересная и, как будто, решение просматривается...

(12 Дек '17 18:36) Urt

@Urt: да, я понял. Интересно, если тут окажется какая-то "идейная" стратегия, а не просто полный перебор.

(12 Дек '17 20:17) falcao
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×1,128
×1,077
×276
×147
×122

задан
12 Дек '17 2:58

показан
656 раз

обновлен
12 Дек '17 20:17

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

по почте:

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

по RSS:

Ответы

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

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