Задача с олимпиады ЮМШ
Feb. 3rd, 2013 05:24 pmВчера прошел очный тур олимпиады ЮМШ. Я его (наглым образом) проболел, но в составлении все-таки поучаствовал. Вот такой вот сюжет был разыгран в 9-м классе. [Здесь я немного уточнил условие, чтобы исключить в первой задаче решение с делением пополам.]
Монетный двор отчеканил 101 монету. С виду они одинаковые, но весить могут по-разному. Известно, что монеток какого-то веса среди отчеканенных больше половины, и они-то и были названы настоящими. У кассира есть чашечные весы без гирь, на каждую чашу которых можно класть только одну монету, и он хочет найти хотя бы одну настоящую.
1.1. В этом пункте считается известным, что настоящих монет ровно 51 и они более тяжелые, а 50 оставшихся также весят одинаково. Как кассиру найти хотя бы одну настоящую монету за 50 взвещиваний?
1.2. Фальшивые монеты могут весить по-разному, количество настоящих монет неизвестно. Как найти настоящую монету за 100 взвешиваний?
1.3. Как найти настоящую монету за 100 взвешиваний, если каждую монету можно взвешивать не более двух раз?
1.4. В этом пункте уже не гарантируется, что монет какого-то веса больше половины. Как за 150 взвешиваний найти хотя бы одну монету из большинства, если оно есть, или же определить, что большинства нет?
Комменты пока будут скрыты. 4-я задача более трудная, чем предыдущие.
Монетный двор отчеканил 101 монету. С виду они одинаковые, но весить могут по-разному. Известно, что монеток какого-то веса среди отчеканенных больше половины, и они-то и были названы настоящими. У кассира есть чашечные весы без гирь, на каждую чашу которых можно класть только одну монету, и он хочет найти хотя бы одну настоящую.
1.1. В этом пункте считается известным, что настоящих монет ровно 51 и они более тяжелые, а 50 оставшихся также весят одинаково. Как кассиру найти хотя бы одну настоящую монету за 50 взвещиваний?
1.2. Фальшивые монеты могут весить по-разному, количество настоящих монет неизвестно. Как найти настоящую монету за 100 взвешиваний?
1.3. Как найти настоящую монету за 100 взвешиваний, если каждую монету можно взвешивать не более двух раз?
1.4. В этом пункте уже не гарантируется, что монет какого-то веса больше половины. Как за 150 взвешиваний найти хотя бы одну монету из большинства, если оно есть, или же определить, что большинства нет?
Комменты пока будут скрыты. 4-я задача более трудная, чем предыдущие.