knop: (qr)
Очередное моё творчество для "Элементов".
http://elementy.ru/problems/1093
На сей раз в качестве задачи выбран сюжет 10.8 из Всероса этого года (авторы - Илья Богданов и Сергей Берлов), хотя доказательство оптимальности я написал по-другому. В "Послесловии" показаны еще две задачки, в которых оптимальность алгоритма доказывается тем же методом - рассмотрением Соперника, который играет против произвольного алгоритма.

Если вы знаете еще какие-нибудь нетривиальные задачи, в решении которых появляется Adversary/Соперник, - напишите, пожалуйста.
knop: (qr)
Про 27 монет известно, что 26 из них настоящие и весят 1 грамм, а ещё одна монета фальшивая и весит m, m+1 или m+2 граммов (где m — натуральное число, известное взвешивающему). Оказалось, что за два взвешивания на чашечных весах без гирь можно определить вес фальшивой монеты. При каком наибольшем m это возможно?

Комменты скрыты.
knop: (qr)
Наша с Таней Ховановой статья вышла. Пока в arXiv. Но метили мы не туда, так что ждем-с основной публикации...
http://arxiv.org/abs/1409.0250
knop: (qr)
Поймал задачу на каких-то дурацких форумах, причем на половине она была с неверным ответом.

"Даны чашечные весы, имеющие особенность — они могут выдержать ровно 3 взвешивания (неважно в каком порядке) неравных грузов, после чего ломаются. Одинаковые веса можно уравновешивать на этих весах бесконечное количество раз. Среди N монет есть одна фальшивая, вес которой меньше настоящих.

Найдите максимальное N при котором можно найти фальшивую не более, чем за 7 взвешиваний на этих весах."

Ответ, который я умею доказывать, - 379.
(Проверьте себя). Контрольный вопрос такой: какое число монет из 379 кладется на чаши весов в первом взвешивании?

Комментарии скрываются
knop: (qr)
См. в "Элементах".
http://elementy.ru/problems/861
Спасибо Тане Ховановой за сюжет и участие в содержательных обсуждениях.
knop: (qr)
Среди 49 одинаковых на вид монет - 25 настоящих и 24 фальшивых. Для определения фальшивых монет имеется тестер. В него можно положить любое количество монет, и если среди этих монет больше половины фальшивых, то тестер подаёт сигнал. Как за пять тестов найти две фальшивых монеты?
(автор - К.Кноп)

Комменты скрыты на несколько дней.
knop: (qr)
Из 239 неотличимых на вид монет две – одинаковые фальшивые, а остальные – одинаковые настоящие, отличающиеся от фальшивых по весу. Как за три взвешивания на чашечных весах без гирь выяснить, какая монета тяжелее – фальшивая или настоящая? Сами фальшивые монеты находить не нужно.

(если кому-то невмоготу глянуть решение, то вот http://problems.ru/view_problem_details_new.php?id=116826)

А теперь вот такое усложнение.
Одна из монет, увы, намертво приклеилась к левой чаше чашечных весов.
Как, несмотря на это, все равно справиться с задачей?

Комменты скрывать не буду, но полные решения, если они будут, скрою.
knop: (uzel)
Таня Хованова уже неоднократно интересовалась у меня, а почему россияне совсем-совсем не участвуют в MIT Mystery Hunt. Пока что у меня нет никакого "правильного ответа", кроме "как-то так, не сложилось".
Тем не менее, в этом соревновании есть очень интересные задачи. Вот пример из моей любимой области:

Среди девяти монет 8 фальшивых и одна настоящая (sic!). При этом какие-то четыре фальшивых одинаковы и весят легче настоящей, а другие четыре фальшивых тоже весят одинаково, но тяжелее настоящей.
Как найти настоящую монету всего за 6 взвешиваний на двухчашечных весах?

Комментарии пока будут скрыты.
knop: (uzel)
Вчера прошел очный тур олимпиады ЮМШ. Я его (наглым образом) проболел, но в составлении все-таки поучаствовал. Вот такой вот сюжет был разыгран в 9-м классе. [Здесь я немного уточнил условие, чтобы исключить в первой задаче решение с делением пополам.]

Монетный двор отчеканил 101 монету. С виду они одинаковые, но весить могут по-разному. Известно, что монеток какого-то веса среди отчеканенных больше половины, и они-то и были названы настоящими. У кассира есть чашечные весы без гирь, на каждую чашу которых можно класть только одну монету, и он хочет найти хотя бы одну настоящую.

1.1. В этом пункте считается известным, что настоящих монет ровно 51 и они более тяжелые, а 50 оставшихся также весят одинаково. Как кассиру найти хотя бы одну настоящую монету за 50 взвещиваний?

1.2. Фальшивые монеты могут весить по-разному, количество настоящих монет неизвестно. Как найти настоящую монету за 100 взвешиваний?

1.3. Как найти настоящую монету за 100 взвешиваний, если каждую монету можно взвешивать не более двух раз?

1.4. В этом пункте уже не гарантируется, что монет какого-то веса больше половины. Как за 150 взвешиваний найти хотя бы одну монету из большинства, если оно есть, или же определить, что большинства нет?


Комменты пока будут скрыты. 4-я задача более трудная, чем предыдущие.
knop: (uzel)
В моём распоряжении - 128 маленьких бусинок, из которых 127 драгоценных (весят одинаково), а одна поддельная (весит чуть легче). Я могу делать какое угодно число взвешиваний на ювелирных чашечных весах у знакомого ювелира, но после каждого взвешивания ювелир забирает себе по одной бусинке с каждой чаши весов, а если какие-то из моих бусинок в этом взвешивании не были положены на весы, то он забирает и одну из таких бусинок. Я хотел бы сделать себе как можно более длинное ожерелье, в котором нет поддельной бусинки. Какого результата я смогу достичь?

Задача не скрыта от всего света, а комменты я пока скрываю. Просьба писать свой конечный результат (длину ожерелья) либо в теме комментария, либо (если оформление вашего LJ не позволяет ставить тему комментария) в первой же строчке. Лучшие текущие результаты буду выносить в постскриптумы к посту.

P.S. Несколько читателей добрались до 116 (я пока не проверял решения), еще несколько до 115, кроме того, представлено одно полупереборное доказательство того, что 115=max.

PPS. Важно! Кажется, я все-таки ошибся с выбором того количества бусинок, при котором эта задача оказывается интересной... Тем, кто в ней добрался до 115 или 116, предлагаю порешать более интересную версию - исходно имеются всего 77 бусинок (76 из них драгоценные, одна поддельная более легкая).
knop: (uzel)
[Кубок Колмогорова, 2010, личная олимпиада 10-11 кл.]

Вася выбрал два различных натуральных числа, не превосходящих 13. Петя пишет на лиcточке пять множеств чисел, а затем Вася напротив каждого из них записывает, сколько в этом множестве задуманных им — ноль, одно или два. Докажите, что Петя не сможет гарантированно определить оба загаданных Васей числа.

Сразу хочу предупредить, что задача весьма трудная, поэтому комментарии скрывать заранее не буду.
knop: (Default)
Пусть n — натуральное число, большее 1. У Кости есть прибор, устроенный так, что если в него положить 2n+1 различных по весу монет, то он укажет, какая из монет — средняя по весу среди по-ложенных. Барон Мюнхгаузен дал Косте 4n+1 различных по весу монет, и про одну из них сказал, что она является средней по весу. Как Косте, использовав прибор не более n+2 раз, выяснить, прав ли барон?

Комменты скрыты. Дети решают эту задачу сегодня - в Москве, Кирове, Омске и Санкт-Петербурге. А я вот дома болею... ;-(
knop: (Default)
Я выложил на http://kknop.com/math/apsimon.html русский перевод статьи Р.Гая и Р.Новаковски об одной "взвешивательной" задаче Х.Апсаймона (Apsimon's Mints Problem), добавив в статью свой маленький постскриптум.

Если кто-то заинтересуется задачкой - пишите идеи. Комменты не скрываю
knop: (Default)
Руководство поставило такую задачу - нужно точно определить вес груза, о котором известно только то, что это целое число от 1 до N. Для этого нам в пользование выделены двухчашечные весы и две гири (какие попросим).

Да, такая задача неразрешима при двузначных N. Но руководство любезно согласилось по нашей просьбе (с которой можно обратиться в любой момент и сколько угодно раз) тут же менять любую гирю на вдвое более тяжелую. Например, начав с гирь массой 1 г и 5 г, мы можем сразу же сравнить вес груза со значениями 1, 5, и 4, а если он окажется меньше 4, то заменить 1 на 2 и сравнить его с 2 и 3 (=5-2).

Какие гири следует заказать вначале, чтобы решить задачу для как можно большего числа N?
knop: (Default)
В отличие от предыдущей геометрии, это простая задача на взвешивания. Предложена на региональном туре олимпиады Эйлера (т.е. 8 классу), номер 3.

На столе лежат 100 одинаковых с виду монет, из которых 85 фальшивых и 15 настоящих. В вашем распоряжении есть чудо-тестер, в который можно положить две монеты и получить один из трех результатов — «обе монеты настоящие», «обе монеты фальшивые» и «монеты разные». Можно ли за 64 таких теста найти все фальшивые монеты?

Комменты скрыты.
knop: (Default)
Сегодня на Уральском турнире (в матбоях, для 8 класса) дали следующую задачу:

Из 10 монет, лежащих в ряд, две соседних - фальшивые, они весят поровну (тяжелее настоящих). Как их найти с помощью двух взвешиваний на одночашечных весах со стрелкой?

Комменты скрыты, хотя для читавших мою книжку могу подсказать, что там в занятии 4 есть усложненный вариант этой задачи ;-)
knop: (Default)

В общем, раз уж я сам ее нашел, то почему б не поделиться. Качайте.
http://ifolder.ru/23531855
knop: (kazan)
Есть 5 монет достоинством 1, 2, 3, 4 и 5 копеек. Вес настоящей монеты в граммах равен ее достоинству, а вес каждой фальшивой - на 0,1 г легче. Из пяти монет две фальшивых, при этом хотя бы одна из монет 1 и 5 является настоящей. Можно ли найти обе фальшивых монеты за два взвешивания на двухчашечных весах (без стрелок и гирь)?
knop: (kazan)
[Эта задача есть в списке дополнительных в моей книжке, но я не помню, чья она - моя, А.В.Шаповалова или совместное с ним творчество... Помню, что мне все время хотелось придумать для книжки хотя бы пару нетривиальных задач на идею "склейки случаев".]

В ряд лежат 8 монет, при этом из левых четырёх одна фальшивая и из правых четырёх тоже одна (обе фальшивые легче настоящих и~равны по весу друг другу). За два взвешивания найдите, сколько настоящих монет лежит между парой фальшивых (сами фальшивые монеты определять не обязательно).

Комменты скрыты

April 2017

S M T W T F S
      1
234567 8
9101112131415
16171819202122
23242526272829
30      

Syndicate

RSS Atom

Style Credit

Expand Cut Tags

No cut tags
Page generated Jul. 25th, 2017 06:29 am
Powered by Dreamwidth Studios