Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/circles/oim/materials/spring06/steel/s07-1-urkud.ps Дата изменения: Fri Apr 7 17:08:00 2006 Дата индексирования: Sun Dec 23 01:29:40 2007 Кодировка: Windows-1251 Поисковые слова: ультрафиолетовое излучение

Линейность над Z 2
Группа Стали, Кудряшов Ю. Г., 07.04.06
Есть табло с n лампочками и k выключателей. При переключении каждого выключателя
некоторый набор лампочек (свой для каждого выключателя) меняет состояние.
Задача 1. Докажите, что число состояний лампочек, которые можно получить из некоторого
начального, есть степень двойки.
Назов?м инвариантом такой набор лампочек, что каждый выключатель меняет состояние
ч?тного числа лампочек из этого набора.
Задача 2. Докажите, что число инвариантов есть степень двойки.
Задача 3. Докажите, что произведение числа инвариантов на число состояний, которые мож-
но получить из некоторого начального, есть 2 n .
Задача 4. Лампочки расположены в виде прямоугольника mЧn. Для каждой лампочки есть
выключатель, который переключает ?крест? с пересечением в этой лампочке.
(a) При каких m, n из любого состояния лампочек можно получить любое другое?
(b) Найдите число состояний, которые можно получить из некоторого начального.
Назов?м соотношением такой набор выключателей, что после переключения всех выклю-
чателей этого набора состояние всех лампочек оста?тся прежним.
Задача 5. Докажите, что число соотношений есть степень двойки.
Задача 6. Докажите, что произведение числа соотношений на число состояний, которые мож-
но получить из некоторого начального, есть 2 k .
1