|
Два игрока по очереди ставят точки в клетки таблицы $%7\times 7$%. За один ход ставится ровно одна точка. В одну клетку может быть поставлено несколько точек (ставить точки на границы клеток нельзя). Проигрывает тот, после чьего хода в клетках какой-то строки или столбца суммарно будут стоять 5 точек. Кто из игроков может обеспечить себе победу независимо от игры соперника? (Минская городская олимпиада) ............................................................ Меня смущает, что в одну клетку может быть поставлено несколько точек, ведь добавление данной детали в условие задачи лишь облегчает её решение! Действительно, вторму игроку для победы достаточно в ответ на ход первого игрока ставить точку в той же самой клетке, что и первый. Изначально таблица пуста (во всяком случае, в условии не указано, что это не так), следовательно, в каждом строке и в каждой столбце чётное число точек. Ход первого игрока нарушает условие чётности (ровно в одной строке и ровно в одном столбце теперь нечётное число точек), а ответный ход второго возвращает всё на круги своя - и снова в каждой строке и в каждом столбце чётное число. Следовательно, первый игрок рано или поздно проиграет. Разве не так? А если изменить условие и запретить ставить в одну клетку более одной точки, что тогда? Пожалуйста, помогите решить. Заранее благодарю! задан 12 Дек '17 2:58 
Аллочка Шакед
показано 5 из 7
показать еще 2
|
Здравствуйте
Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Присоединяйтесь!
отмечен:
задан
12 Дек '17 2:58
показан
821 раз
обновлен
12 Дек '17 20:17
Связанные вопросы
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
@Аллочка Шакед: может быть, потому и добавили, что в противном случае получается сложная задача? С ходу непонятно, к то выиграет, и какова стратегия. Я пробовал применять какие-то соображения, но общей картины пока не складывается. Хотя условие звучит весьма естественно и интересно.
@falcao, мне конопляжется, что второй игрок в ответ на каждый ход первого должен ставить точку в той же строке, что и первый, но в том столбце, в котором менее 4 точек. Тогда количество точек в каждой строке после хода второго будет чётным, а столбец с менее 4 точками для второго игрока всегда найдётся, так как если после хода первого игрока в одном из столбцов будет 5, то первый уже проиграл, а ровно по 4 в каждом столбце после хода первого игрока быть не может, так как 7*4=28 чётное число, а после хода первого игрока общее число точек нечётно.
НУ И ГДЕ У МЕНЯ ОШИБКА???
@Аллочка Шакед: попытки сформулировать стратегии такого типа у меня были, но ни к чему не привели. То, что Вы описали, по-моему, не достаточно. Почему не может так оказаться, что у второго игрока не найдётся хода? Он должен ставить точку в клетке определённой i-й строки, где какие-то поля свободны. Общее число сделанных ходов в этот момент нечётно. Но почему не может оказаться, что во всех столбцах, для которых клетки i-й строки свободны, имеется ровно по 4 клетки? Ведь отсюда следует чётность только по этим столбцам, а не по всей таблице.
При числе точек меньше 28 всегда найдется строка, куда можно поставить точку, ... и столбец, конечно, тоже. Можно разрешить первому поставить сразу 14 точек. От этого результат не изменится. Мне подсказали контрпример с квадратами 4х4 и 3х3. Этот комментарий не удаляю,... становится интересно.
@Urt: понятно, что при количестве меньше 28 найдётся "хорошая" строка, а также "хороший" столбец. Но у меня это рассуждение ещё вчера "упёрлось" в то, что на их пересечении место уже может оказаться занято. Можно ли преодолеть эту трудность?
Случай 3x3 я прослеживал, а 4x4 не смотрел. Контрпримеры к какому утверждению Вы имели в виду?
@falcao, контрпример к неподкрепленному другими посылками заключению о том, что при наличии хорошей строки и хорошего столбца найдется и хорошая клетка. Задачку увидел сегодня - решил сделать небольшой (так, на 5-10 мин.) перерыв и отвлечься от дел..., но этот процесс затягивается. Задача интересная и, как будто, решение просматривается...
@Urt: да, я понял. Интересно, если тут окажется какая-то "идейная" стратегия, а не просто полный перебор.