Найдите все пары натуральных чисел (a, b), удовлетворяющие одновременно следующим условиям:
1) Дробь a/b несократима и имеет в десятичной записи вид 0,(xy). То есть 0,xyxyxy.... Здесь x и y - это цифры.
2) Дробь (a+1)/(b+1) в десятичной записи имеет вид 0,(z). То есть 0,zzz.... Здесь z - это цифра.
Эту картинку я нарисовал недавно с помощью искусственного интеллекта (ChatGPT). Причём идею картинки я, кажется, где-то подсмотрел очень давно. Впрочем я не уверен. Если кто-то из вас видел подобную картинку, сообщите мне, пожалуйста.
Есть куча из N камней. Играют двое людей, делающих ходы по очереди. За один ход игрок разделяет кучу на две части произвольным образом, но так чтобы в каждой части был хотя бы один камень. После этого второй игрок убирает в сторону любую из частей на своё усмотрение. Оставшаяся часть становится новой кучей. Далее ход переходит ко второму игроку. То есть теперь второй игрок разделяет новую кучу на две части, а первый игрок убирает одну из частей. И так далее. Проигрывает тот игрок, который не может сделать ход.
Вопросы:
Найдите выигрышную стратегию.
На картинке ниже мальчик делает ход. Почему девочка так хитро улыбается, глядя на мальчика?
Если задача вам понравилась, то посмотрите похожую задачу «Раздели и оставь». Правила игры там несколько отличаются. В результате ответ на задачу совершенно другой.
На столе лежат 5 монет. За один ход нужно перевернуть любые 3 монеты. При перевороте монета, лежавшая ранее решкой вверх, будет лежать орлом вверх. А лежавшая орлом вверх будет лежать решкой вверх.
В начале все монеты лежат решками вверх. Можно ли за несколько таких ходов добиться, чтобы все монеты оказались орлами вверх? То есть все монеты должны перевернуться относительно своего изначального положения. Если это возможно, то каково минимальное количество ходов?
Ответы пишите в комментариях к этой публикации.
Курьер должен развезти заказы с пиццами в 7 домов, расположенных вдоль прямой дороги. В начале дороги находится пиццерия, откуда курьер должен забрать пиццы. Первый дом находится в 1 километре от пиццерии. Второй дом - в том же направлении от пиццерии, но в 2 километрах. Третий дом - в 3 километрах. И так далее. Седьмой дом находится в 7 километрах. Смотрите картинку.
Рюкзак курьера вмещает не более 3 заказов. Курьер стартует из пиццерии. Он может возвращаться в пиццерию сколько угодно раз. В конце он должен вернуться в пиццерию.
Вопрос: Какое минимально возможное расстояние должен проехать курьер, чтобы развезти все 7 заказов?
Есть квадратное поле, на котором расположены 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 конфигурации состояний ламп.
