Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/circles/oim/materials/sbory05/tablperm.doc Дата изменения: Tue May 3 12:50:31 2005 Дата индексирования: Sun Dec 23 00:34:23 2007 Кодировка: koi8-r Поисковые слова: п п п п п п п п

Таблицы.

Плюсы и минусы.
0. В клетках таблицы 2Nx2N некоторым образом расставлены плюсы и минусы.
За ход можно изменить знак во всех клетках любого «креста», то есть
объединения некоторых строки и столбца. Докажите, что за несколько
ходов можно получить таблицу, во всех клетках которой стоят плюсы.
1. В клетки таблицы mxn вписаны некоторые числа. Разрешается одновременно
менять знак у всех чисел некоторой строки или некоторого столбца.
Докажите, что многократным повторением этой операции можно превратить
данную таблицу в такую, у которой суммы чисел, стоящих в любой строке
и в любом столбце, неотрицательны.
2. Во всех клетках шахматной доски 8х8 расставлены плюсы, за исключением
одной не угловой клетки, где стоит минус. Разрешается одновременно
менять знак во всех клетках одной горизонтали, одной вертикали или
одной диагонали (диагональ - линия по которой ходит шахматный слон).
Докажите, что такими операциями невозможно получить доску с одними
плюсами.
3. В каждой клетке таблицы nxn стоят минусы. За один ход можно поменять
знаки в одной фигуре Z-тетрамино. При каких n можно получить таблицу
со всеми плюсами?

Оценка.
4. Шахматная доска 6х6 покрыта 18 костями домино 2х1. Докажите, что при
любом таком покрытии можно разрезать доску на две части по
горизонтальной или вертикальной линии, не повредив ни одной кости
домино.
5. Можно ли расставить цифры 0, 1, 2 в клетках таблицы 100х100 таким
образом, чтобы в каждом прямоугольнике 3х4 клетки оказалось 3 нуля, 4
единицы и 5 двоек?

Пример+оценка.
6. Какое наибольшее число дамок можно расставить на шашечной доске 8х8
так, чтобы каждая дамка билась хотя бы одной другой дамкой?
7. Какое наименьшее число фишек нужно поставить на поля шахматной доски
размером
а) 8х8
б) nxn
для того, чтобы на каждой прямой, проходящей через центр произвольного
поля и параллельной какой-либо стороне или диагонали доски, стояла
хотя бы одна фишка?
8. Какое наименьшее число уголков из трех клеток нужно разместить в
квадрате 8х8 клеток, чтобы в него нельзя было поместить без наложения
ни одной такой фигуры?
9. В квадрате 7х7 клеток нужно отметить центры К клеток так, чтобы
никакие 4 отмеченные точки не являлись вершинами прямоугольника со
сторонами, параллельными сторонам квадрата. При каком наибольшем К это
возможно?