 |
ОКТЯБРЬ 2008-ЯНВАРЬ 2009
“ШАРАДА 120”
Бюллетень клуба ценителей головоломок “Диоген”.
Подготовлен к печати 09.01.2009. Леонтьева. Рыбинским в 1993-м г. Автор эмблемы - Сергей Грабарчук. Тираж 60 экз.
119607 Москва, Мичуринский пр.
( (095)
*****@***ru
www.diogen.h1.ru
С Новым годом, уважаемые друзья-головоломщики!
Удачи вам во всех начинаниях, с оптимизмом смотреть на будущее. Предлагаем вашему вниманию новогоднюю открытку-поздравление от семьи Грабарчуков.
Перед вами ёлка, украшенная гирляндами шаров. Заполните шары цифрами от 1 до 7, чтобы в каждой из четырёх гирлянд все цифры встречались по разу. Цифры не должны повторяться также в каждой прямой линии, параллельной одной из сторон ёлки.
ПЯТНАДЦАТЫЙ ЗАОЧНЫЙ ЧЕМПИОНАТ РОССИИ ПО РЕШЕНИЮ ГОЛОВОЛОМОК
Решения в произвольной форме отправляйте до 31 марта 2009 года на адрес 119607 Мичуринский пр. д. 35 кв. 115 или e-mail *****@***ru . Просьба самостоятельно подсчитать и указать свой результат в каждой задаче.
1. ВЕЛОПРОБЕГ-2009 (Ш 505)
Трое друзей должны преодолеть расстояние 200 км. У них есть один велосипед с багажником. Скорость у каждого, когда он идет пешком – 5 км\ч, когда едет на велосипеде в одиночку – 15 км\ч, когда на велосипеде едут двое – 10 км\ч. Велосипед можно останавливать (в том числе и для того, чтобы ссадить или подсадить еще одного человека) только у километровых столбиков, то есть ровно через 1, 2, 3,… км от начала пути. Его можно оставлять без присмотра (тоже только у километровых столбиков). За какое наименьшее время друзья смогут преодолеть расстояние? Округлите результат до минут.
Оценка: 50 баллов за лучшее решение, 45 – за следующее, 40 – за следующее и т..д..
2. СЕМЬЯ-2009 (Ш 506)
Прошедший год был годом семьи. Поместите в сетке 12 слов, обозначающих родственников:
БАБУШКА
БРАТ
ВНУК
ВНУЧКА
ДЕДУШКА
ДОЧЬ
ЖЕНА
МАТЬ
МУЖ
ОТЕЦ
СЕСТРА
СЫН
Пример для трех слов в сетке 5х7:
Каждое слово должно быть написано на отдельной полоске, прямой или изогнутой (переход от буквы к букве через сторону клетки), которая не может касаться ни себя, ни других полосок. При этом все буквы в каждой строке и каждом столбике сетки должны быть различными. Постарайтесь использовать прямоугольную сетку наименьшей площади.
Оценка: 50 баллов за лучшее решение, 46 – за следующее, 42 – за следующее и т. д.
3. КОМПЛЕКТ ПЕНТАМИНО (Ш 507)
Расположите полный комплект пентамино в сетке 12х12. Элементы можно поворачивать и переворачивать, они не должны касаться друг друга даже углом.
Вы должны описать расположение элементов, пометив некоторые клетки пустой сетки 12х12 черным, как принадлежащие элементу, а в некоторые другие – поставив крест, означающий, что в этой клетке элемента нет. По этому описанию положение каждого элемента должно определяться однозначно. За каждую черную клетку вы получаете 3 очка, за каждую пустую – 2 очка. Ваша задача – набрать как можно МЕНЬШЕ очков. Например, вы можете отметить все 60 черных клеток (этого будет достаточно для однозначности) и получить 180 очков. Или отметить крестиком все 84 пустые клетки и получить 168 очков:
Оценка: 50 баллов за лучшее решение, 47 – за следующее, 44 – за то, что за ним и т. д..
4. КУБИК (Ш 508)
Прокатите игральный кубик по квадрату 8х8, начав с угла. Не обязательно посещать все клетки, но нельзя дважды проходить через одну. Перекатив кубик в очередную клетку, запишите в ней число на верхней грани кубика. В начальной клетке будет записано 1. Кубик стандартный, сумма очков на противоположных гранях равна 7.
Сделайте сумму всех 64 (или менее) чисел максимальной.
Пример: при указанном движении кубика сумма в посещенных клетках равна 224.
Оценка: 50 баллов за наибольшую сумму, 48 – за следующую, и т. д..
5. ЛИНИЯ В ОБЛАСТИ (Ш 509)
На клетчатой плоскости обозначьте область площади 100 (возможно – сложной формы, с внутренними пустотами). Затем проведите линию через центры клеток по следующим правилам:
Линия начинается в любой клетке и идет прямо, пока не упирается в границу области. Там она поворачивает вправо или влево и идет прямо, пока не упирается в другую границу области, и т. д. Линия может пересекать себя, но не должна второй раз проходить по своему участку. Линия прекращается, когда уже не может быть продолжена с соблюдением указанных условий. Проведите линию как можно большей длины.
Пример: линия длины 26 в области площадью 23.
Оценка: 50 баллов за лучшее решение, 44 – за следующее, и т. д..
ИТОГИ МАТЧА РОССИЯ-УКРАИНА 2008
Р1. ВЕСЫ (Ш496)
Победа россиян, предложивших решение за 13 ходов.
Описание алгоритма Константина Кнопа, где объясняется план решения за 13 ходов и первые 4 хода по нему:
Для удобства мы будем считать, что весы имеют не две, а три чашки (на третью кладутся все те монеты, которые в данном взвешивании не участвуют). Число монет на чашках 1 и 2 должно быть одинаковым, а для чашки номер 3 это не обязательно. Результатом каждого взвешивания является выявление более легкой из трех чашек. [Если весы исправны, то ФМ находится именно на легкой чашке, а если испорчены - то на какой угодно.]
Если мы произвели взвешивание на K-х весах (K=1,2,3,4,5), то
монеты, лежащие НЕ на легкой чашке, мы будем называть К-отказниками. [Смысл этого названия - в том, что К-е весы ОТКАЗАЛИ данным монетам в возможности быть
фальшивыми.] Объединение множеств K-отказников по всем K
назовем ОДИНАРНЫМИ отказниками. Если какому-то подмножеству монет отказали и весы K, и весы L, такие монеты мы будем называть (K, L)-отказниками (а объединение таких отказников по всем парам (K, L) - ПОВТОРНЫМИ отказниками).
Наконец, если каким-то монетам отказали трое и более весов, эти монеты точно не являются фальшивыми (точнее, являются заведомо настоящими - независимо от того, какие именно весы испорчены).
Монеты, которым еще не отказали ни одни весы, мы будем называть "подозреваемыми".
Важнейшее соображение для алгоритма решения состоит в том,
что отыскать фальшивую монету означает ПЕРЕВЕСТИ ВСЕ ОСТАЛЬНЫЕ В КАТЕГОРИЮ ЗАВЕДОМО НАСТОЯЩИХ. Никакого другого пути отыскания
ФМ не существует: пока есть хотя бы две монеты среди подозреваемых, одинарных или двойных отказников, - любая из них может быть фальшивой (при каком-то выборе неисправных весов).
Далее. Описываю основной рабочий инструмент для поиска алгоритма. Введем специальную числовую функцию - ЗНАЧИМОСТЬ монеты. В грубом приближении, значимость равна количеству вариантов, в которых данная монета является фальшивой. Зададим эту функцию следующим образом:
значимость подозреваемой монеты = 2t^2 + 1 значимость ОДИНАРНОГО отказника = 2t + 1 значимость ПОВТОРНОГО отказника = 1 значимость настоящей монеты = 0,
где t - число взвешиваний, которое ОСТАЛОСЬ ПРОДЕЛАТЬ до
конца алгоритма. Значимостью взвешивания будем называть сумму значимостей всех участвующих в нем монет.
Смысл этой функции - в том, что она позволяет на каждом взвешивании следить за тем, чтобы значимость взвешивания сокращалась втрое (хотя бы примерно, точность не нужна).
Действительно, пусть в нашем распоряжении имеются ВЕСЫ,
СВОБОДНЫЕ ОТ ОТКАЗНИКОВ, т. е. весы с таким номером K,
что нет ни одинарных K-отказников, ни повторных (K, L)-отказников ни для какого номера L. После взвешивания на этих весах подозреваемые монеты могут остаться подозреваемыми (оказавшись на легкой чаше)либо стать K-отказниками (оказавшись на двух других чашах). С точки зрения функции значимости, это означает, что значимость каждой монеты стала либо равной 2(t-1)^2+1, либо (два раза) 2(t-1)+1. В силу тождества 2t^2 +1 = 2(t-1)^2+1 + (2t-1) + (2r-1) это означает, что сумма возможных значимостей этой монеты после
данного взвешивания такая же, как и значимость монеты до взвешивания.
Аналогично, одинарные отказники L-го типа могут либо остаться
таковыми (со значимостью 2t-1), либо стать KL-отказниками
(два исхода, каждый имеет значимость 1). И здесь также работает тождество 2t+1 = 2t-1 + 1 + 1, поэтому значимости монеты "до" и "после" одинаковы.
Наконец, то же самое верно для двойных отказников - они либо
остаются таковыми (если попали на легкую чашу весов), либо
оказываются тройными отказниками, а значит, заведомо настоящими, и в этом случае их значимость уже равна 0.
Таким образом, сумма значимостей монет до взвешивания равна сумме их значимостей после всех трех возможных исходов этого взвешивания. Следовательно, если мы (за счет выбора раскладки монет на чашки) сделаем значимости всех трех исходов равными, то мы поделим значимость втрое, а это нам и нужно (выписанная в предыдущем письме оценка показывает, что делить значимость более чем втрое не удастся никаким алгоритмом!). Когда мы (в результате ряда взвешиваний) доведем значимость взвешивания
до 1, это будет означать, что у нас имеется всего одна монета, не являющаяся заведомо настоящей. Именно она и есть искомая ФМ. Разумеется, в этом случае никакое взвешивание больше не нужно - это полностью соответствует тому, что для t=0 нет разницы между подозреваемыми и отказниками:
2*0^2 + 1 = 2*0 + 1 = 1.
Начальная ситуация - 2008 подозреваемых монет, каждая имеет значимость 339 (2*13^1+1).
Еще одно полезное рабочее соображение.
Мы будем говорить об (a, b,c, d)-ситуации, если у нас
перед очередным взвешиванием имеется a подозреваемых
монет, b одинарных отказников, c двойных отказников
и d заведомо настоящих монет.
Если для двух ситуаций (a1,b1,c1,d1) и (a2,b2,c2,d2) выполняются неравенства a1 >= a2, a1+b1 >= a2+b2
и a1+b1+c1 >= a2+b2+c2 (а также, очевидно, еще и равенство
a1+b1+c1+d1 = a2+b2+c2+d2), и первая ситуация
позволяет нам отыскать ФМ за необходимое число ходов,
то и вторая ситуация это позволяет. Действительно,
мысленно перекинем часть монет из d2 в c2, чтобы
уравнять a2+b2+c2 с a1+b1+c1; после этого аналогично
перекинем часть монет из c2 в b2, уравнивая a2+b2 с a1+b1, и, наконец, перекинем недостающее из b2 в a2. Этим мы полностью свели ситуацию 2 к ситуации 1. Далее отыскиваем ФМ для ситуации 1 по алгоритму. Какой бы ни оказалась эта монета, она же будет и единственно возможной ФМ для второй ситуации, потому что этим перекидыванием мы всего лишь "забыли" о части результатов ранее проведенных взвешиваний, а именно, о том, что какие-то монеты уже получали отказы от каких-то весов. Собственно, все. Осталось лишь предъявить конкретный алгоритм взвешиваний, аккуратно подсчитывая в нем значимости после каждого исхода, сравнивая ситуации в различных исходах при помощи приведенного
выше "полезного рабочего соображения" и выбирая на следующее взвешивание наиболее тяжелую ситуацию.
Дополнительно при реализации алгоритма (и это самое непростое!) нужно следить за тем, чтобы на каждом шаге у нас имелись хотя бы одни весы, свободные от отказников.
Ради этого имеет смысл даже жертвовать точностью дележа
значимости на 3: если отказников определенного типа в какой-то
момент оказалось чересчур много, то часто полезнее их все
оставить на одной чашке, чем дробить на разные и тем самым
увеличивать число типов отказников, присутствующих в каком-то
из исходов.
Первые четыре хода наиболее очевидны:
1. (2008,0,0,0) делим на три почти равных кучки, взвешиваем
на весах 1, в худшем случае получаем (670,1338,0,0).
2. Переходим на весы 2, делим и 670, и 1338 на равные кучки,
в худшем случае получаем (224,446+446,892,0); здесь "+"
означает то, что первые 446 являются 1-отказниками, а вторые -
2-отказниками.
3. Переходим на весы 3, снова все делим поровну, получаем ситуацию
не хуже, чем (75,149+149+149,297+297+297,595).
Здесь имеются одинарные отказники типов 1, 2 и 3, а также
повторные отказники типов 12, 13 и 23.
4. Переходим на весы 4, делим поровну 75 подозреваемых,
а остальные - уже не делим: на одну чашу кладем 149 1-отказников
и к ним же 297 (1,2)-отказников, на другую - столько же 2- и
(2,3)-отказников, на третью - столько же 3- и (3,1)-отказников.
Без ограничения общности можно считать, что легкой оказалась чашка 1. В результате получаем перед пятым взвешиванием следующую ситуацию: (25,149+50,297+149+149,1189).
Далее уже приходится аккуратно выбирать типы отказников, поэтому единообразие и симметричность оказываются нарушенными. Тем не менее, не более чем через три хода мы уменьшаем число "подозреваемых" (неотказников) до 1 (а дальше избавляемся от них вообще или сразу же находим ФМ), еще за 3 хода (или меньше) находим ФМ или избавляемся от всех одинарных отказников, а за последние 3 хода - доводим до 1 число двойных отказников.
Р2. СУДОКУ-ОПТИМАЙЗ. (Ш497)
Победа россиян, предложивших решение с суммой 259.
В сетке отмечены цифры в посещенных клетках, остальные цифры восстанавливаются без проблем.
.
Последовательность движения:
Л – влево
П – вправо
В – вверх
Н – вниз
Начиная с центральной клетки Е5:
E5-Л-В-П-Н-Л-В-П-Н-Л-П-В-Н-В-Л-П-Н-В-Л-П-Н-В-Н-Л-В-Н-Н-В-П-В-П-Л-В-П-Л-Л-П-Н-Л-Л-В-Н-В-П-Л-Н-В-П-Н-В-Н-В-Н-Л-П-Н
Р3. УГОЛКИ (Ш498)
Победа россиян, предложивших решение за 14 ходов
1. c4-d3 f8-e8
2. a1-b1 h5-g4
3. c2-d2 h7-g6
4. a4-b5 g6-c4
5. a2-e6 f5-e4
6. d3-f5 g7-a1
7. b2-f8 h6-b2
8. a3-g7 f7-d3
9. b4-h6 g5-a3
10. c3-g5 h8-b4
11. d2-h8 e4-a4
12. b5-h5 e8-a2
13. b1-h7 g4-c2
14. e6-f7 d3-c3
Р4. ПЕНТАОПТИМАЙЗ(Ш 499).
Победа украинцев, у которых S=10.
C | C | C | F | F | P | P | P | ||||
C | C | F | F | P | P | ||||||
F | L | ||||||||||
I | I | I | I | I | L | L | L | L | |||
X | |||||||||||
X | X | X | T | ||||||||
J | W | X | T | T | T | ||||||
J | J | W | W | T | |||||||
J | W | W | Z | ||||||||
J | V | Z | Z | Z | |||||||
V | Y | Z | |||||||||
V | V | V | Y | Y | Y | Y |
У1. МНОГО ТОЧЕК (Ш 500).
Ничья, обе команды нашли лучшее решение:
 |
Точки образуют два квадрата и 8 правильных треугольников.
У2. МНОГО БУКВ (Ш 501).
Победа россиян, 136 букв в словах
ДЖХУКАР | ЛИЧНОСТЬ | ВЫПРЯДКА | ЮБИЛЕЙНОСТЬ |
ЛИНЮЧЕСТЬ | РЯПУШКА | ГНИЮЧЕСТЬ | ВЫПРЯЖКА |
ЦЫПУШКА | НЕМИЛОСТЬ | УПРЯЖКА | ЭЛЕГИЧНОСТЬ |
ЛЮБЕЗНОСТЬ | ШКУРЁХА | БЕЗЛИЧНОСТЬ | ХУДЫШКА |
У3. ТРОЙКИ (Ш 502).
Победа россиян, нашедших судоку с 10 задающими тройками и 2 решениями:
У4. КОНЬ В СУДОКУ (Ш 504).
Победил российский конь, обошедший 48 клеток начиная с левого верхнего угла. Отмечены числа в клетках, посещенные конем. Остальные цифры, как и путь коня, вычисляются без труда.
Поздравляем россиян, победивших с общим счётом 6,5 - 1,5.
Просим присылать задачи и идеи задач для следующего матча.
ЧЛЕНЫ НАШЕГО КЛУБА
В Шараде-118 публиковался список членов клуба Диоген. За прошедшее время несколько человек добавили свои анкеты. Спешите сделать то же самое, если не сделали до сих пор. Итак, знакомимся с новыми членами клуба (нумерация списка продолжается).
55. , Ростовская обл.
*****@***ru
Дата рождения - 09.12.1954.
Учитель математики, любитель решать, ценитель и коллекционер головоломок и книг. В коллекции около 500 головоломок. Есть библиотечка книг о головоломках и занимательной математике. Имеет публикации в журналах "Наука и жизнь", "Квант", "Шарада", проводит конкурсы по решению головоломок в местной газете, делает выставки головоломок в школах, стоял у истоков создания нашего клуба (номер 15 в списке В. Рыбинского).
56., Ленинградская обл.
Дата рождения - 15.05.1952
Психолог, любитель решать головоломки
57., Вологда
Дата рождения - 14.11.1948
Гончар, коллекционер головоломок и книг, ценитель головоломок
Изготовитель сосудов с секретами. Есть коллекция механических головоломок.
58., Истра
e. *****@***ru
Дата рождения - 22.12.1978
Любитель решать, коллекционер головоломок и книг, составитель и изобретатель. Большая коллекция головоломок ( механические).
59., Псков
kost. *****@***ru
Дата рождения - 29.07.1971
Оперуполномоченный, любитель решать, коллекционер книг, составитель и исследователь головоломок, ценитель. Коллекция механических головоломок – около 550 штук, книг о разных головоломках около 200 штук. Предпочтение в решении головоломок – механические, а в составлении - словесных и логических, сотрудничает с ООО "Логос-Медиа" имеет публикации.
60., Мытищи
Дата рождения -09.04.1937
Преподаватель и педагог, любитель решать, коллекционер книг, ценитель головоломок. Собиратель занимательного независимо от области знания, деятельности. Библиография занимательной литературы, материалы о популяризаторах и т. п.
61., Владимирская обл.
Дата рождения -08.02.1949
Военный пенсионер, составитель, изобретатель и исследователь головоломок.
62., Москва
*****@***ru
Дата рождения - 08.08.1974
Маркетолог, любитель решать головоломки, сотрудник фирмы по производству/продаже головоломок.
63., Москва
*****@***ru
Дата рождения -29.01.1986
Учитель начальных классов. Любитель решать, исследователь головоломок, учитель математики, прежде всего, нестандартной (нешкольной) программы. Любит геометрические головоломки на размещение, задачки на разрезание.
64. , Тольятти
*****@***ru
Дата рождения 01.04.1951
Инженер-механик, электросварщик. Любитель решать, коллекционер головоломок и книг о головоломках, отчасти составитель/изобретатель головоломок, по мере способностей исследователь, ценитель.
Есть небольшие (порядка 500) коллекция механических головоломок, 2-3 сотни книг по головоломкам. Наибольший интерес представляют «пятнашки», танграмы, словесные головоломки
КЛУБУ "ДИОГЕН" – 15 ЛЕТ
13 декабря в редакции журнала "Наука и жизнь" состоялась 15-я встреча членов клуба "Диоген" и их гостей. На встречу собралось около 40 человек.
В 2008 году клубу исполнилось 15 лет. В настоящий момент в клубе состоит 64 члена из многих городов России и четырех других стран. Пятеро из них вступили в клуб как раз во время декабрьской встречи. О том, чем занимается клуб и как в него попасть, можно узнать на сайте клуба http://diogen. *****/, который организован и поддерживается благодаря Андрею Богданову.
Декабрьская встреча, конечно, была парадом механических головоломок. Началась она с традиционного обмена головоломками. Несмотря на некоторые ужесточения правил (запрет на обмен бумажными головоломками и книгами), в обмене участвовало 15 человек. Каждый участник представил свою головоломку, а для тех, кто не участвовал в обмене, головоломки были доступны на демонстрационном столе.
Все собравшиеся по очереди рассказывали о новостях за прошедший год.
завершил книгу о загадочных картинах и рисунках. Мы с нетерпением ждем ее выхода в 2009 году. также представила книги, автором которых она является ("300 сражений в "Морской бой", "300 модных головоломок: судоку, какуро, хитори", "Головоломки для взрослых и очень умных", "Игры и головоломки в дорогу для дружной компании" и др.).
сообщил, что стал заниматься головоломками профессионально. Теперь он является заведующим лабораторией инновационных игр в Московском городском Дворце детского (юношеского) творчества на Воробьевых горах. Он организовал музей-студию головоломок и каждую первую субботу месяца проводит праздники головоломок для всех желающих (подробнее см. http://www. *****).
, приехавшая из Минска и участвовавшая в обмене головоломками, рассказала о проведении в Минске 17 чемпионата мира по паззлспорту. Главный организатор чемпионата вместе с немногочисленной командой помощников были поставлены в трудные условия – необходимо было срочно организовать чемпионат, поскольку намеченная заранее страна-организатор отказалась от его проведения. В результате чемпионат был не только спасен, но и проведен на высоком уровне. Подробный рассказ о чемпионате будет в одном из ближайших номеров Шарады.
В августе 2008 года в Праге состоялся 28 съезд любителей головоломок со всего мира (28 International Puzzle Party). На съезде присутствовала большая команда представителей клуба "Диоген": Гребнев, Жиров, Красноухов, Матвеева, Новичкова, Певницкий, Прелуцкий. А вообще был установлен рекорд по количеству участников – 400 человек. Все, кто был на съезде, с удовольствием вспомнили и рассказали о событиях "головоломной" недели в Праге и показали самые новые, необычные, увлекательные и остроумные головоломки, привезенные оттуда.
принес на встречу интересные композиции из Кирилл Гребнев показывает свою головоломку букв, написанных таким образом, что в них можно прочитать разные слова, поворачивая или переворачивая рисунок. Он устроил импровизированный конкурс по чтению упрятанных в рисунке слов.
Братья Михаил и Антон Ростовиковы из Балашихи в этом году привели в клуб своих друзей Бедризенко Антона и Ежова Максима. Все вчетвером ребята устроили мини-соревнование по скоростной сборке кубика Рубика. Как и в прошлом году самым быстрым оказался Антон Ростовиков, который получил приз-головоломку.
А вообще призы получили все участники встречи, поскольку в завершение встречи была проведена беспроигрышная лотерея с призами-головоломками. После фотографирования на память народ разошелся по домам, унося новые впечатления, а также желание еще не раз вновь окунуться в этот манящий мир головоломок.
РАЗНОЕ
***
Уважаемые друзья! Вы можете подробно рассказать о себе и своей деятельности, ознакомить других членов клуба с интересующими вас проблемами и головоломками, поделиться идеями и достижениями. Пишите на адрес редакции!
***
Восьмого февраля состоится очередной чемпионат России по решению судоку. Приглашаются все желающие. Более подробная информация – на сайте клуба.
В выпуске:
ПЯТНАДЦАТЫЙ ЗАОЧНЫЙ ЧЕМПИОНАТ РОССИИ ПО РЕШЕНИЮ ГОЛОВОЛОМОК | 4-7 |
ИТОГИ МАТЧА РОССИЯ-УКРАИНА | 8-14 |
НОВЫЕ ЧЛЕНЫ КЛУБА | 15-16 |
ДЕКАБРЬСКАЯ ВСТРЕЧА КЛУБА | 17-19 |
