Квадраты двух последовательных натуральных чисел отличаются лишь перестановкой последних трёх цифр (без неподвижных точек). Найдите эти числа.
Есть квадратное поле, на котором расположены 9 лампочек в 3 ряда и 3 столбца. Изначально все лампочки выключены. Разрешено выбрать один ряд и переключить все лампочки в нём. При переключении лампочка меняет состояние: выключенная лампочка становится включённой, а включённая становится выключенной. Также разрешено выбрать один столбец и переключить все лампочки в нём.
Вопросы:
Можно ли после некоторого числа таких действий получить любую конфигурацию состояний лампочек?
Если — можно, то предложите алгоритм получения произвольной конфигурации.
Если нельзя получить любую конфигурацию, то сколько всего различных конфигураций можно получить, начиная от состояния «все выключены»?
Ниже привожу моё авторское решение этой задачи. Советую вам сначала попытаться решить задачу самостоятельно, и только потом читать моё решение.
Посчитаем, сколько всего существует различных конфигураций состояний лампочек. Лампочек у нас 3×3 = 9 штук. Каждая лампочка может быть в 2 различных состояниях: либо включена, либо выключена. Значит, количество различных конфигураций состояний всех 9 лампочек будет 2^9 = 512.
Посчитаем теперь, скольких конфигураций можно достичь, следуя условиям задачи. У нас есть 3 ряда. Над каждым рядом можно произвести 2 различных действия: либо ничего не делать, либо переключить. Нет смысла рассматривать действие, состоящие из 2 или более переключений. Дело в том, что чётное число переключений эквивалентно отсутствию переключения, а нечётное — одному переключению. То же самое и с 3 столбцами. Т.е. всего различных наборов действий 2^(3+3) = 2^6 = 64. Однако может быть, что разные наборы действий приводят к одинаковым конфигурациям. Тогда число достижимых конфигураций будет меньше. Давайте посчитаем, сколько именно.
Обозначим действие над i-ым рядом как Ряд(i). Действие может принимать значение 0 или 1. Здесь 0 означает, что нет переключения. А 1 означает, что есть переключение. Аналогично обозначим действие над j-ым столбцом как Столб(j). Каждый набор действий можно записать 6 числами: {Ряд(1), Ряд(2), Ряд(3), Столб(1), Столб(2), Столб(3)}.
Обозначим состояние лампы в i-ом ряду и j-ом столбце как Лампа(i,j). Значение 0 означает, что лампа выключена, а 1 — что включена. Напомним, что изначально все лампы выключены. Тогда после применения какой-либо набора действий лампа окажется в состоянии Лампа(i,j) = (Ряд(i)+Столб(j)) mod 2, здесь mod 2 означает остаток от деления на 2. Всего есть 4 набора действий над одной лампой: {Ряд(i), Столб(j)} = {0,0}, {0,1}, {1,0}, {1,1}. Однако приводить эти 4 действия могут только к 2 различным состояниям лампы: 0 и 1. Действия {0,0} и {1,1} приводят к одному и тому же состоянию 0, т.е. выключено. А действия {0,1} и {1,0} приводят состоянию включено. Таким образом для каждого набора действий над всеми лампами {Ряд(1), Ряд(2), Ряд(3), Столб(1), Столб(2), Столб(3)} есть другой набор {1-Ряд(1), 1-Ряд(2), 1-Ряд(3), 1-Столб(1), 1-Столб(2), 1-Столб(3)}, приводящий к той же конфигурации состояний ламп. Все прочие наборы действий, кроме указанных двух, будут приводить к другим конфигурациям. Итак, достижимых конфигураций состояний ламп в 2 раза меньше, чем наборов действий. Т.е. количество конфигураций состояний ламп 64/2 = 32.
Итак, произвольную конфигурацию состояний ламп получить нельзя. Но как получить любую из достижимых конфигураций? Допустим, нам задана некая конфигурация. Попробуем получить её. Рассмотрим верхний ряд лампочек. Переведём все эти 3 лампочки в требуемое состояние, переключая, если нужно, соответствующие столбцы. Теперь рассмотрим самый левый столбец. Верхняя лампочка в нём уже находится в правильном состоянии. Переведём среднюю и нижнюю лампочки из этого столбца в требуемые состояния, переключая, если нужно, средний и/или нижний ряд. Итак, всего мы перевели в требуемое состояние 5 лампочек. Остались ещё 4 лампочки, которые мы уже не можем переключить, не портя состояние первых 5 лампочек. Если оказалось, что эти 4 лампочки находятся в правильном состоянии, то мы достигли нужной конфигурации. Если нам не повезло, и они в неправильном состоянии, то такой конфигурации достичь невозможно.
Как было показано выше, существует ещё один набор действий, приводящий к тому же результату. А именно если первый набор мы обозначим {Ряд(1), Ряд(2), Ряд(3), Столб(1), Столб(2), Столб(3)}, то второй будет {1-Ряд(1), 1-Ряд(2), 1-Ряд(3), 1-Столб(1), 1-Столб(2), 1-Столб(3)}. Вспомним, что в первом алгоритме мы гарантированно не переключали верхний ряд, т.е. Ряд(1)=0. Вернёмся к исходной конфигурации, когда все лампы выключены. Теперь переключим верхний ряд, т.е. выполним действие 1-Ряд(1)=1. Далее повторим описанный выше алгоритм: выставим лампочки верхнего ряда в правильные состояния, переключая соответствующие столбцы, и так далее. Нетрудно заметить, что так мы опять гарантированно получим 5 лампочек в правильном состоянии. Остальные 4 лампочки — как повезёт. Ранее мы доказали, что все лампочки окажутся в том же состоянии, что и при применении первого алгоритма. Т.е. если первый алгоритм выставил 4 последние лампочки в правильное состояние, то и второй выставит их правильно. Таким образом, у нас есть 2 набора переключений, которые приводят к нужной конфигурации состояний ламп, если эта конфигурация принципиально достижима.
Итак, ответы на вопросы задачи следующие:
1. Нет, не всякую конфигурацию состояний ламп можно получить указанным в задаче способом.
2. Алгоритма получения произвольной конфигурации состояний ламп не существует. Алгоритм получению любой из достижимых конфигураций описан выше.
3. Всего достижимы 32 конфигурации состояний ламп.
Сколько пятизначных чисел, делящихся на 4, можно составить из цифр 1,2,3,5, если требовать, чтобы каждая из этих цифр встретилась хотя бы раз?
Построение 4, 5, 6 измерения на основе декартовых счисления, не думаю, что это есть правильно. Эти построения основаны на повторяемости, а это есть работа мозга увидеть новое в старом обличии. Моё мнение, эти измерения в декартовых счисления не соответствуют указанным выше измерениям.
Существуют ли 6 различных чисел, таких что их сумма равна их произведению?
У Насти есть несколько красивых камушков (не обязательно равных по весу). Для каждого натурального n, не превышающего 5, Настя может распределить эти камушки на две группы так, что камушки в одной группе будут в n раз тяжелее, чем в другой. Какое наименьшее число красивых камушков может быть у Насти?
Разрежьте изображённую на рис.1 фигурку на две части, из которых можно сложить треугольник.
