Ферматизм XXI

Вряд ли это можно считать головоломкой. Тем более любимой. И все равно я не понимаю, откуда их столько...

Решение Великой теоремы и тайна уравнения Ферма - купить в OZON.ru	Великая теорема Ферма. Арифметическое решение - купить в OZON.ru	Великая теорема Ферма. Исследование проблемы - купить в OZON.ru
Решение Великой теоремы Ферма для нечетных степеней - купить в OZON.ru	Тайна Великой теоремы - купить в OZON.ru	Второй вариант решения Великой теоремы Ферма для нечетных степеней - купить в OZON.ru
Новые методики в арифметике целых чисел - купить в OZON.ru

Ребусик

(A^G+AG)^G = GAAGA.

AG - двузначное число, GAAGA - пятизначное. 

Задача Гальперина об одномерном бильярде

Можете попробовать проверить свою математическую интуицию в следующей задаче.

Легкий шар массы m расположен между стенкой и тяжелым шаром массы M. В этой задаче шары могут двигаться только в одном измерении: либо к стенке, либо от нее. Тяжелый шар толкнули по направлению к стенке. Сколько в этой системе произойдет столкновений (со стенкой и между шарами), если M = 10^N·m. (Все соударения мгновенные и абсолютно упругие.) Начните с частных случаев а) N=1, б) N=2.

Ответ и детальное решение приведены в статье Евгения Епифанова http://elementy.ru/problems/595 . Ответ лично мне кажется удивительно неожиданным.

ОЧР-2013 по паззлспорту

Очный чемпионат России состоится 22 июня 2013 г. в Москве.

Место проведения - Дворец Творчества "Неоткрытые острова".Начало регистрации участников - в 10.30. При себе иметь карандаш, ластик и бумагу для черновиков.

Заявки на участие - по адресу olgainna@rambler.ru.

Более подробная информация и условия задач скоро появятся на сайте www.diogen.h1.ru

Разрезать семиугольник на три подобных четырёхугольника

https://docs.google.com/file/d/0ByXEl13981ctd3dUczBXeHk4eGs/edit

Разрезать на подобные фигуры

Перед вами - правильный треугольник со стороной 16 (для удобства визуально разделенный на треугольники со стороной 2), из которого вырезан единичный правильный треугольник. Разрежьте эту фигуру на две подобных друг другу фигуры, коэффициент подобия которых равен 2.

  

И "прямоугольная" версия той же задачи. 

Взвешивание на двух весах

Преамбула 

Возможно, вы слыхали о том, что такое puzzlesport. То бишь "чемпионаты по решению головоломок". В рамках этого вида спорта бывают и совсем диковинные звери - заочные соревнования, в которых некоторое небольшое число задач решается в течение многих недель и даже месяцев, причем допускаются и приветствуются командные решения. Вот именно таким соревнованием является ежегодный традиционный матч между Россией и Украиной, посвящённый памяти Андрея Ходулёва.

Так уж сложилось, что от России почти каждый год бывает какая-нибудь "монетная" задачка, и чаще всего - сделанная с моим участием. В силу специфики матча мы даем на него порой очень сложные сюжеты. Однако в прошлом году ничего интересного из сложных сюжетов я не придумал, и предложил банальную вариацию классики - одновременное взвешивание на нескольких весах. То есть "параллельные вычисления".

Вот условие матчевой задачи

У нас есть N внешне неразличимых монет (из которых одна фальшивая, неизвестно, легче или тяжелее остальных, все настоящие монеты весят одинаково) и ДВОЕ рычажных весов, взвешивания на которых мы можем делать параллельно. Каждое такое параллельное взвешивание на двух весах длится одну минуту. Для какого наибольшего числа монет N удастся отыскать фальшивую за 5 минут (время на перекладку монет для следующего взвешивания считаем пренебрежимо малым)?

Согласитесь, вариация очень естественная (лично для меня было удивительно то, что она новая).
Ниже - авторское решение.

Ответ: для 1561 монеты. [Комментарий: (5^5-3)/2.]

Алгоритм взвешиваний.

Будем описывать взвешивания в нотации A-B-C-D-E, где A и B - количества монет, которые в нём кладутся на чаши первых весов, C и D - количества монет на чашах вторых весов, а E - количество ПОДОЗРИТЕЛЬНЫХ монет, которые в этом взвешивании отложены и участия не принимают.
После каждого взвешивания мы будем отслеживать, сколько осталось подозрительных монет и каковы они. Типов подозрительных монет может быть всего три: ФЛ "может оказаться фальшивой лёгкой", ФТ "может оказаться фальшивой тяжёлой" и ФЛТ "может оказаться фальшивой, как лёгкой, так и тяжёлой". До первого взвешивания все монеты отнесены к типу ФЛТ.

1 минута. 312-312-312-312-313.

Результатов взвешиваний может быть пять (<=, >=, =<, =>, ==), но принципиальных случаев два -
А. Каждые весы остались в равновесии.
  Наш вывод: все монеты на весах настоящие (это даёт нам большой запас настоящих монет, который пригодится в следующих взвешиваниях), 313 монет остались типом ФЛТ.
Б. На каких-то весах неравенство.
  Наш вывод: все монеты других весов и все 313 отложенных монет - настоящие (см. выше
комментарий о запасе); 312 монет с более лёгкой чаши отнесены к типу ФЛ, 312 монет с более тяжёлой чаши отнесены к типу ФТ.

Итого после первой минуты мы свели задачу либо к "предыдущей" (для 4 минут и 313 монет, при этом у нас есть запас настоящих монет, назовём это подзадачей А4), либо к такой: "имеется 312 монет типа ФЛ и 312 монет типа ФТ, найти фальшивую за 4 минуты" (назовём её подзадачей Б4).

А4: имеется 313 монет ФЛТ и запас настоящих, надо найти фальшивую за 4 минуты
Б4: имеется 312 монет ФЛ, 312 монет ФТ и запас настоящих, найти фальшивую за 4 минуты.

Дальнейшая схема такова - за очередную минуту сводим подзадачу А_n либо к А_{n-1}, либо к Б_{n-1} в зависимости от результата взвешиваний, а подзадачу Б_n - всегда к Б_{n-1}.

А3: имеется 63 монеты ФЛТ и запас настоящих, найти фальшивую за 3 минуты
А2: имеется 13 монет ФЛТ и запас настоящих, найти фальшивую за 2 минуты
А1: имеется 3 монеты ФЛТ и запас настоящих, найти фальшивую за 1 минуту

Б3: имеется 63 (62) монеты ФЛ и 62 (63) монеты ФТ, найти фальшивую за 3 минуты
Б2: имеется 13 (12) монеты ФЛ и 12 (13) монеты ФТ, найти фальшивую за 2 минуты
Б1: имеется  3 ( 2) монеты ФЛ и  2 ( 3) монеты ФТ, найти фальшивую за 1 минуту

Дальше мы разберёмся с решениями всех этих задач "от простых к сложным".

Решение задачи А1 тривиально: 1-(0+1Н)-1-(0+1Н)-1; здесь "0+1Н" означает, что на чашу кладётся одна заведомо настоящая монета. Если весы покажут равновесие, то фальшивой является отложенная монета.

Решение задачи Б1 тоже совсем просто: (1ФЛ+1ФТ)-(0+2Н)-(1ФЛ+1ФТ)-(0+2Н)-1; здесь "1ФЛ+1ФТ" означает, что на чашу кладутся две монеты - одна ФЛ и одна ФТ. На другую чашу кладутся две настоящих. Если весы покажут равновесие, то фальшивой является отложенная монета - она может быть как ФЛ, так и ФТ. Если же одни весы покажут неравенство, то по его знаку мы сразу определим, какая из подозрительных монет действительно фальшивая.

Сведение задачи Б2 к Б1: (3ФЛ+2ФТ)-(3ФЛ+2ФТ)-(2ФЛ+3ФТ)-(2ФЛ+3ФТ)-5.
Отложенные монеты могут быть либо 3ФЛ и 2ФТ, либо 3ФТ и 2ФЛ. Если какие-то весы покажут неравенство, то подозрительными остаются ФТ-монеты с более тяжёлой чаши и ФЛ-монеты с более лёгкой. В любом исходе получается набор монет, удовлетворяющий условию Б1.
Аналогично сводится Б3 к Б2 и Б4 к Б3.

Сведение задачи А2 к А1 или Б1: (2+1Н)-3-(2+1Н)-3-3. Здесь "2+1Н" - это две ФЛТ-монеты и одна настоящая. После равновесия получаем А1, а после неравновесия - Б1.
Аналогично сводится А3 к А2 и А4 к А3.

Статья о задаче "Крест и полумесяц"

50+49

99 мудрецов сели за круглый стол. Им известно, что пятидесяти из них надели колпаки одного из двух цветов (белого или чёрного), а сорока девяти остальным - другого (но заранее неизвестно, какого именно из двух цветов 50 колпаков, а какого 49). Каждый из мудрецов видит цвета всех колпаков, кроме своего собственного. Все мудрецы должны одновременно написать (каждый на своей бумажке) цвет своего колпака. Смогут ли мудрецы заранее договориться отвечать так, чтобы не менее 74 из них дали верные ответы? 

Разрезалка

Пятиугольник представляет собой прямоугольник 6x8, к которому слева добавлен равнобедренный прямоугольный треугольник с гипотенузой 6.

Попробуйте разрезать такой пятиугольник на две подобных, но не равных, фигуры.