Математический форум Math Help Planet
http://mathhelpplanet.com/

Инфекция на шахматной доске
http://mathhelpplanet.com/viewtopic.php?f=50&t=71070
Страница 1 из 1

Автор:  anton-petrunin [ 06 сен 2020, 07:16 ]
Заголовок сообщения:  Инфекция на шахматной доске

Задача приведённая ниже включена в книжку Питера Винклера с таким замечанием:
«Эта милая задача впервые появилась в советском журнале "Квант" где-то в 1986 году, а затем перекочевала в Венгрию.»

Мне хотелось бы найти точную ссылку.
Я пролистал "Квант" за 1985---1987 годы и ничего похожего не нашёл (мог пропустить, но вряд ли).
Если что-то известно про Венгрию, то мне тоже интересно.

Инфекция распространяется по клеткам шахматной доски следующим образом: если у клетки два или более инфицированных соседа, то она также заражается. (Соседями считаются только клетки с общей стороной, так что у каждой клетки имеется максимум четыре соседа.) Докажите, что нельзя заразить всю шахматную доску, если изначальное число инфицированных клеток меньше 8.

Автор:  Student Studentovich [ 06 сен 2020, 14:27 ]
Заголовок сообщения:  Re: Инфекция на шахматной доске

anton-petrunin
Хорошая задачка на инварианты. Вам решение или ссылку?

Автор:  anton-petrunin [ 06 сен 2020, 21:39 ]
Заголовок сообщения:  Re: Инфекция на шахматной доске

Оракул

Решение я знаю, мне бы ссылку.

Автор:  Student Studentovich [ 07 сен 2020, 00:54 ]
Заголовок сообщения:  Re: Инфекция на шахматной доске

anton-petrunin
Ловите. http://www.irmo.ie/combinatorics_chessboard.pdf
Problem 5

Автор:  anton-petrunin [ 07 сен 2020, 04:44 ]
Заголовок сообщения:  Re: Инфекция на шахматной доске

Оракул

Спасибо, но это явно поздний вариант и источник там не указан.

Автор:  anton-petrunin [ 28 сен 2020, 20:56 ]
Заголовок сообщения:  Re: Инфекция на шахматной доске

Эта задача с Московской олимпиады 1986 года.
В Кванте она действительно была:
Квант 1986, № 8, с. 57, http://kvant.mccme.ru/1986/09/olimpiada.htm

По Венгрии есть пара ссылок:
    Gábor Pete: Hogyan gyepesítsünk kockát? Polygon (Szeged) VII:1 (1997), 69--80.
    József Balogh and Gábor Pete, Random Disease on the Square Grid (1997)

Страница 1 из 1 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/