К. Кноп

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

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

Задача №3. Дан выпуклый пятиугольник $ABCDE$, причём прямая $BE$ параллельна прямой $CD$ и отрезок $BE$ короче отрезка $CD$. Внутри пятиугольника выбраны точки $F$ и $G$ таким образом, что $ABCF$ и $AGDE$ — параллелограммы. Докажите, что $CD = BE + FG$. ( С. Берлов, К. Кноп )
комментарий/решение(1) олимпиада

Задача №4. Среди 49 одинаковых на вид монет — 25 настоящих и 24 фальшивых. Для определения фальшивых монет имеется тестер. В него можно положить любое количество монет, и если среди этих монет больше половины — фальшивые, тестер подает сигнал. Как за пять тестов найти две фальшивых монеты? ( К. Кноп )
комментарий/решение(1) олимпиада

Задача №5. У Зевса имеются весы, позволяющие узнавать вес положенного на них груза, и мешок со 100 монетами, среди которых есть 10- и 9-граммовые. Зевсу известно общее число $N$ 10-граммовых монет в мешке, но неизвестно, какие именно сколько весят. Он хотел бы сделать четыре взвешивания на весах и в результате гарантированно найти хотя бы одну 9-граммовую монету. При каком наибольшем $N$ это возможно? ( К. Кноп )
комментарий/решение(1) олимпиада

Задача №6. Дана окружность длины 90. Можно ли отметить на ней 10 точек так, чтобы среди дуг с концами в этих точках имелись дуги со всеми целочисленными длинами от 1 до 89? ( К. Кноп )
комментарий/решение(1) олимпиада

Задача №7. Устройство КК42 работает так: если положить в него четыре шарика, то в первый лоток вывалится второй по весу шарик (т.е. шарик веса $b,$ если $a > b > c > d)$, а во второй лоток вывалятся остальные. С другим числом шариков устройство не работает. Имеются 100 одинаковых на вид шариков попарно различных весов. Их пронумеровали числами $1, 2, \ldots, 100.$ Как, использовав прибор не более 100 раз, найти самый тяжелый шарик? ( К. Кноп )
комментарий/решение(1) олимпиада

Задача №8. У царя Гиерона есть 13 металлических слитков, неразличимых на вид; царь знает, что их веса (в некотором порядке) равны 1, 2, $\ldots,$ 13 кг. Ещё у него есть прибор, в который можно положить один или несколько из имеющихся 13 слитков, и он просигналит, если их суммарный вес равен ровно 46 кг. Архимед, знающий веса всех слитков, хочет написать на двух слитках их веса и за два использования прибора доказать Гиерону, что обе надписи правильны. Как действовать Архимеду? ( К. Кноп )
комментарий/решение(1) олимпиада

Задача №9. У ювелира есть 100 золотых монет. Покупатель знает лишь, что веса этих монет равны 1, 2, $\ldots$, 100 г в каком-то порядке, а ювелир знает, какая сколько весит. Как ювелиру за два взвешивания на чашечных весах без гирь доказать покупателю, что известная ювелиру однограммовая монета действительно весит 1 г, но при этом не дать покупателю возможности определить вес никакой другой монеты? ( К. Кноп )
комментарий/решение(1) олимпиада

Задача №10. Квантовый компьютер расходует 1 кВт/ч электроэнергии на каждую сделанную им операцию умножения или сложения. При этом он умеет хранить результаты промежуточных действий. Докажите, что для любых пяти хранящихся в компьютере чисел $a$, $b,$ $c$, $d$, $e$ можно найти сумму $ab+ac+ad+ae+bc+bd+be+cd+ce+de$, затратив не более 10 кВт/ч. ( К. Кноп )
комментарий/решение(2) олимпиада

Задача №11. Есть две кучки по 11 монет в каждой. Известно, что в каждой кучке 10 настоящих монет и одна фальшивая, которая легче настоящей. Все настоящие монеты весят одинаково, обе фальшивые — тоже. Можно ли за одно взвешивание на чашечных весах гарантированно найти не менее 8 настоящих монет? ( К. Кноп )
комментарий/решение(1) олимпиада