Индукция:
- для одной очевидно
- предположим верность для всех возможных графов с 1...n лампочек и докажем для всех возможных графов с n+1:

1. обозначим одну из лампочек А
2. воспользуемся тем алгоритмом, который включает остальные n лампочек
3. если А включена, то закончили
4. выключим все лампочки, кроме А, и проделаем шаги 1-3 для каждой из остальных лампочек.

5. если мы дошли до этого шага, то во всех случаях оказалось, что изменение состояния любых n лампочек не влияет на оставшуюся
6. проделаем шаги 1-2
7. обозначим еще одну произвольную лампочку Б
8. проделаем шаг 2 для всех лампочек, кроме Б. Теперь А и Б включены, а остальные - выключены.
9. воспользуемся тем алгоритмом, который включает остальные n-1 лампочек
10. если А и Б остались включенными, то закончили
11. если А и Б выключились, то вернемся в исходное состояние и проделаем шаг 9 над всеми, кроме А и Б; закончили
12. Пусть Х - это та лампочка из {А, Б}, которая осталась включенной. Проделаем шаг 2 над всеми лампочками, кроме Х, и закончили.

Отличное решение, браво!

Мне оно тоже нравится, но в последнем шаге ошибка :)

Попытка №2, тоже индукция, для n+1:
1. Покажем, что утверждение верно для четного n+1.
2. Покажем, что для нечетного n+1:
2.1. Есть хоть одна лампочка А, переключение которой влияет на нечетное количество лампочек (включая А).
2.2. Поэтому утверждение верно для нечетного n+1.

1. Воспользуемся алгоритмом из первого поста, кроме последнего шага. 2 включены.
Назовем 2-й шаг из первого поста T(x).
Обозначим еще одну лампочку x3, выполним T(x3). Теперь 3 выключены.
Обозначим еще одну x4, выполним T(x4). Теперь 4 включены.
...
Обозначим x_{n-1}, выполним T(x_{n-1}). Теперь n-1 выключены => 1 включена => T(x_n), done.

2.1. Если для всех i = 1...n+1 переключение x_i влияет на четное количество лампочек, то sum(degree(x_i)) - нечетное число. Но известно, что в любом связанном графе sum(degree(x_i)) = 2*(общее количество ребер).
2.2. Поэтому есть такая лампочка (x1), переключение которой включает нечетное количество лампочек (k). Пусть l=n+1
Включим x1 => k включено.
T(x1) => нечетное l-k+1 включено
Обозначим выключенную x2, T(x2) => нечетное k-2 включено
Обозначим включенную x3, T(x3) => нечетное l-k+3 включено
Обозначим выключенную x4, T(x4) => нечетное k-4 включено
...
Обозначим включенную x_k, T(x_k) => l-k+k = l включено

Надеюсь, на этот раз верно :)

Edited at 2009-03-31 13:05 (UTC)

Ах, черт, действительно :) я как раз знал решение, к которому вы пришли - с этой разбивкой - и решил было, что вы нашли проще.

"разбивкой" [spoiler]!!!

Ладно, заскриню, хотя по-моему фигня это, а не спойлер.

У меня дурная привычка: все задачи решать в уме, а записывать уже когда все готово. И не могу отучиться -- как только начинаю записывать, сразу тону в деталях, к этому привыкнуть надо. Ну а когда все продумано, то проверять уже лень :)

Условие у задачи некорректное. Если есть одна вершина, замкнутая сама на себя одним ребром, то её переключить, невозможно, хотя в составе более сложной картинки это не обязательно проблема. Надо требовать, чтобы для каждой вершины нашлась хоть одна другая, с которой она соединена нечётным кол-вом рёбер (а если рассматривать действие вершины самой на себя, тогда наоборот чётным, включая ноль.(*)) Нижеследующее решение не только учитывает возможность вершине соединяться с собой, но вообще подходит к вопросу с другого конца.
Запишем граф в виде симметрической матрицы F. 0 на диагонали соответствует нечётному кол-ву ребер замыкающих соответствующую вершину саму на себя, 1 - чётному. Вне диагонали наоборот, нечётное количество связей - пишем 1, чётное -0. Y - вектор, каждая компонента которого даёт количество переключений соответствующего тумблера. Произведение матрицы на вектор даёт другой вектор, все компоненты которого, должны быть нечётны, чтобы переключение произошло, я для конкретики буду требовать, что они все единицы. Имеем систему линейных уравнений на компоненты Y, все коэффициенты 0 или 1, все свободные члены (справа от равенства) единицы. Решаем систему складывая, вычитая, и умножая на -1 уравнения. В результате имеем Y итые - целые числа. Они могут быть отрицательными, но это не важно - важна чётность. Если Y итый четный - тумблер включать не нужно, если нечётный - 1 раз. Если среди уравнений были линейно зависимые - будет произвол дополнительный, он нам не мешает. Возможная линейная зависимость даёт ответ на вопрос, почему этот метод гарантированно годиться только для полного переключения, иначе воможно например: Y1+Y2=1, Y1+Y2=0; Условие * необходимо, т.к. иначе будет 0=1.
Если объяснение непонятное, могу прислать nb файл, где я конкретный пример разобрал.

Другими словами, задачка с на первый взгляд очень богатым внутренним миром свелась к рутиннейшему методу Гаусса.

а откуда следует, то решение системы должно быть целым?

Можно уже разскринить, по-моему.

Если это не очень сложно доказать для произвольного графа (я пока не придумал, как), отчего здесь трудности?

As shown by Sutner (1989), going from all lights on to all lights off is always possible for any size square lattice.

Для клетчатой доски это простейшая линейная алгебра, там просто уж очень подробно расписано.

"Вначале все лампочки выключены." - это ключевой момент

Вот я и спрашиваю, почему ж тогда доказательство было только для квадратных досок?

"Вначале все лампочки выключены." - это ключевой момент

going from all lights on to all lights off

Какая разница, в какую сторону?

> avva: Не очень сложная, не очень простая.
Задача с клетчатой доской довольно простая. По крайней мере нам её рассказывали в 10м классе (Не знаю, такое же доказательство как у Sutner (1989), или нет).

Давайте сведём задачу к похожей, но чуть посложнее:

Пусть A_{ij} - матрица n x n, в которой i-th row/j-col равен i-th row/j-th col матрицы смежности графа, остальное - "0".
Вопрос: является ли L - матрица из "1" линейной комбинацией (коэфф., понятно, в Z/2Z) A_{ij}?

Теперь надо по свойствам A_{ij}, которые будут следовать из свойств матриц смежности, понять то же, что и в оригинальной задаче.

Я пошёл спать.

А можно не чисто математическое решение?

1. Если мы считаем, что скорость распространения возмущений в графе бесконечна (включение лампочки МОМЕНТАЛЬНО приводит к загоранию сосенских лампочек, которые МОМЕНТАЛЬНО включают свои соседские) - любой граф по определению или включен или выключен.
2. Если мы считаем, что скорость распространения конечна - например, соседские лампочки включаются ТОЛЬКО НА СЛЕДУЮЩЕМ ЦИКЛЕ, - доказать возможно только для односвязанных графов. На многосвязанных графах возможно образование циклов (петель), по которым порожденная волна может ходить вечно (теоретически, имея обратную связь о состоянии графа, можно погасить эту "волну". Но сам факт циркуляции волны при внесении первоначального возмущения приводит ук мысли о невозможности доказательства задачи).

Мне так кажется. Как практику. Вспоминая механизмы разводки печатных плат в системах проектирования :)

This obviosly maps into system of linear equations (over Boolean field with "xor" and "and"): C <s0, ..., sN> = <1,... ,1> where C is the binary graph connectivity matrix and s are switches (0-not pushed, 1-pushed once). Obviosly, there's no need to push any switch more than once.

Since C is a symmetric matrix, it can be diagonalized by change of basis (i.e. replacemet of single switches with "accords"). This guarantees that equations are consistent.

Also, since C has diagonal of all 1s, null rows (needed to exclude solution of all 1s) are impossible.

This means that at least one solution of this system of linear equations exists. Finding the solution is trivial (by Gaussian elimination, for example).

At the moment I'm not sure that symmetric matrices over F_2 are diagonalizable, but aside from that

>Also, since C has diagonal of all 1s, null rows (needed to exclude solution of all 1s) are impossible.

I may be misunderstanding, but.

Take the matrix for a complete graph. You get all 1's in the original, but once you diagonalize it you get a lot of zeros. There is a huge kernel. You can not use Gaussian elimination.

However, of course you just need to show that <1,...1> is in the image, i.e. orthogonal to the kernel. This is not hard.

очевидно, что начальное состояние - все выключены - очень важно, иначе в графе - все со всеми задача не решается

ага.

Число рёбер графа = сумма валентностей/2

Поэтому, если все валентности нечётные, то количество вершин обязано быть чётным.

Валентность вершины нечётная тогда и только тогда, когда после нажатия ВСЕХ выключателей (по одному разу - далее подразумевается везде) лампочка в этой вершине останется тёмной.

Отсюда вывод: если после нажатия всех выключателей все лампочки остались тёмными - то количество вершин в графе - чётное.

Переходя к подграфу, получаем следующее утверждение: если множество вершин V графа таково, что после нажатия выключателей в каждой вершине множества V лампочка в каждой вершине V осталась тёмной - то множество V содержит чётное число вершин.

Ослабим это утверждение слегка: если множество вершин V таково, что после нажатия выключателей в каждой вершине множества V вообще все лампочки останутся тёмными, то множество V содержит чётное число вершин.

Рассмотрим матрицу инцидентности нашего графа; обозначим её через A. Мы будем рассматривать её как матрицу над полем F_2 из двух элементов. Тогда любую строку U соответствующего размера можно отождествить с некоторым множеством вершин (а именно, тех вершин, для которых соответствующий элемент строки равен 1). Предыдущее утверждение записывается так: если U(A+1) = 0, то U содержит чётное число единиц.

Пусть Y - столбец из сплошных единиц. Тогда предыдущее утверждение переформулируется в виде U(A+1) = 0 => UY = 0. Рассматривая матрицу A+1 как линейный оператор в пространстве столбцов, получаем, что любой линейный функционал, обнуляющийся на образе этого оператора, обнуляется на Y. Отсюда Y принадлежит образу этого оператора, то есть, существует столбец X, для которого (A+1)X = Y. Это означает, что если нажать выключатели в вершинах, для которых соответствующий элемент X равен 1, то загорятся все лампочки - что и требовалось доказать.

Вы хорошо подумали?
A->B->C->D->A - четыре вершины (четное к-во)
После последовательного нажатия на выключатели в вершинах A,B,C,D все лампочки будут гореть :)

Где это противоречит тому, что я сказал?

Да, Вы правы, я - нет :(

Наконец-то прочитал и проверил. Красиво. Спасибо!

Отличная задачка, с первого раза я сдох. Хотя потом оказалось, что сдох не по делу, просто поленился додумать.

Возьмем минимальный (по числу вершин) контрпример.
Из минимальности следует, что мы можем включить все лампочки, кроме любой одной. Если число вершин n четно, то этого уже достаточно: эти множества образуют базис всего пространства состояний (оно - векторное пространство размерности n над полем из двух элементов).
Если n нечетно, то они порождают подпространство коразмерности 1 (только множества четного размера). Но тогда есть вершина четной степени, и ее шарик имеет нечетный размер - значит, опять порождено все пространство, в том числе и состояние, когда все лампочки включены.

По сути, это то же доказательство, что и первое приведенное, но без ненужных деталей.

Была на эту тему заметка в МатПросе.

Предположим противное. Тогда вектор из всех единиц не выражается (над Z_2) через векторы "вершина и все соседи", то есть существует однородная линейная функция, разделяющая их: на векторе из всех 1 она единица (то есть у нее нечетное число единичных коэффициентов; отметим соответствующие им вершины), а на каждом векторе вершины она равна нулю (в частности, каждая отмеченная вершина имеет нечетное число отмеченных соседей). Значит, в графе на отмеченных вершинах нечетое число нечетных вершин - противоречие.