Задачи без звездочки

[Dendr]

Давайте, что ли, чего полегче попробуем, после предыдущих мозговых штурмов.

1. В магазине продаются свечи. Большие горят один час и стоят 60 рублей. Маленькие, соответственно, 11 минут и 11 рублей.
Нужно отмерить ровно одну минуту. Во сколько обойдется самая экономная покупка при таких условиях?
Прим. Считается, что свечи горят совсем неравномерно или у нас нет линейки, так что резать их на дольки - не ответ

2. Дано 6 монет. Известно, что среди них есть одна фальшивая (причем ее вес неизвестен, как и вес настоящих монет). Даны также электронные весы.
Как за три взвешивания найти фальшивую монету?
UPD В условии имеется в виду, что весы имеют только одну чашу и могут показывать вес помещенных в нее монет (с требуемой для решения точностью).

[Юляша]

По первой задаче удалось спуститься по шкале 241 - 186 - 148

[Юляша]

По второй задаче, если монеты обозначить ABCDEF, то, последовательно взвешивая монеты AB, CD и ACE, можно установить, какая из них фальшивая. Вес фальшивой монеты при этом, возможно, останется неизвестным, но этого вроде и не спрашивалось).

[Dendr]

Вот это именно сюда. Хотя я месяц на нее убил, так ни к чему и не пришел. А оказалось, что перемудрил сам себя: решение умещается в один абзац.

Вдруг кто-то окажется сообразительнее?

Итак: даны n чисел, которые попарно взаимно просты. Для любого из этих них известно, что если разделить произведение всех остальных чисел на выбранное, то в остатке получается одно и то же число r.
Доказать: r<=n-2.

P.S. Собственно, легко доказывается, что для n=3 существует только единственный набор: 2, 3, 5. Остаток при этом равен 1, что подтверждает условие задачи. Для больших n я доказать ничего не смог, но написал программу, которая выдавала такие наборы числе для разных n и сравнительно небольших чисел в наборе. Для n=4 нашлось два набора, как и для n=5. А вот для шести наборы не нашлись... И во всех случаях наименьшее число равнялось 2, соответственно, остаток - 1.

И пока неизвестно, можно ли доказать, что всегда r=1. Однако, повторюсь, утверждение r<=n-2 доказывается несложным образом.

[Dendr]

Не понравилась? Или не пошла?

Тогда возвращаюсь к разминочным задачкам.

1. Дано 10 гирек. Известно, что любые четыре из них перевешивают любые три из оставшихся. Верно ли утверждение, что любые три гирьки перевешивают любые две из оставшихся?

2. В наборе 20 гирь различной массы (т.е. попарно различной). Известно, что среди любых 11 гирь найдутся две, суммарная масса которых равна сто грамм. Доказать, что суммарная масса всего набора 1 кг. (личное пожелание - дайте решение поизящнее)

[Юляша]

Не понравилась? Или не пошла?

Тогда возвращаюсь к разминочным задачкам.

1. Дано 10 гирек. Известно, что любые четыре из них перевешивают любые три из оставшихся. Верно ли утверждение, что любые три гирьки перевешивают любые две из оставшихся?

2. В наборе 20 гирь различной массы (т.е. попарно различной). Известно, что среди любых 11 гирь найдутся две, суммарная масса которых равна сто грамм. Доказать, что суммарная масса всего набора 1 кг. (личное пожелание - дайте решение поизящнее)

0. Не пошла. Вначале показалось, что легко построить контрпример, - и получились числа 3, 8, 22, которые, очевидно, не взаимно простые.

1. Конечно. И доказательство очень простое - буквально в пару гирек).

2. Стоит упорядочить гирьки по весу, как все становится ясно. (А возможен ли контрпример, если гири могут быть одинаковыми, но ни одна из гирь не весит ровно 50 грамм?)

[Dendr]

Вначале показалось, что легко построить контрпример

Мне тоже так казалось, кучу бумаги извел.
На самом деле, доказательство, буквально, в две строки (надо только ввести дополнительные определения), приведу его прямо здесь.

Пусть такой набор есть, и обозначим его элементы a1, a2, ... an, а произведение всех чисел набора - P.
Теперь ведем "частичные" произведения, то есть Pj=P/aj и рассмотрим число S=P1+P2+...+Pn. Рассмотрим остаток от деления S на, допустим, a1.

По построению P2+...+Pn делится на a1, а P1 имеет остаток r. Следовательно, число S-r делится на a1. Легко продолжить, и увидеть, что оно делится и на все числа набора. А так как они взаимно просты, то S-r делится и на P. Если учесть, что S-r>0, то видно, что S=r+N*P, где N - какое-то натуральное число.
В частности, это значит, что S>=P (не исключаем автоматически случай r=0), или S/P>=1.

Иначе можно написать так: 1/a1+1/a2+...+1/an>=1. Из этого видно, что в сумме должно существовать слагаемое, которое больше, чем 1/n. (если это не так, то только одно из них равно 1/n, остальные - менее 1/n, и сумма последних меньше чем (n-1)/n, а общая - меньше 1)
Без ограничения общностей можно считать, что 1/a1 > 1/n, то есть a1<n. Так как a1 - натуральное, то нестрогое равенство выглядит, как a1<=(n-1).
Так как остаток всегда меньше делителя, то можно достоверно утверждать, что r<a1. Следовательно, r<=(n-2). QED

[Dendr]

Стоит упорядочить гирьки по весу, как все становится ясно.

Вариант, конечно, но мне не очень понравилось. Но контрпример при таком подходе придумать, конечно, легче: берем набор 8х25 грамм, 8х75, 2х40, 2х60. Если в выборке нет ни одной гири по 25 грамм, то есть наверняка пара 40+60 (из 12-гирьного набора 8х75+2х40+2х60 убирается ровно одна гиря). Если нет ни одной гири по 75 грамм - аналогично. Если есть хотя бы одна 25-граммовая и хотя бы одна 75-граммовая - то они и составляют искомую пару.
(Не то написал... надо подумать)

Я такое решение составил: если известно, что среди любых 11 гирь есть две, суммарная масса которых составляет 100 грамм, то и для любых 12 это тоже, и для 13, ... и для 20.
Берем 20 гирь - среди них обязательно есть две, суммарная масса которых равна 100 грамм. Допустим, мы их выбрали - помечаем одну красным маркером, другую синим. Среди 18 непомеченных гирь ни одна не совпадает по массе ни с синей, ни с красной, поэтому "стограммовых" пар ни для той, ни для другой нет.
Отложим в сторону красную гирю и рассмотрим 19 остальных. Среди них, по условию, есть две, которые в сумме составляют 100 грамм, и обе они не помечены. Помечаем их, как в предыдущем акте, и убираем снова красную в сторону.

Повторяем так 9 раз. В итоге остаются 9 синих гирь, 9 красных (в стороне) и 2 непомеченных. Причем ни одна из 11 гирь, что еще в опыте (непомеченные + синие), не совпадает по массе ни с одной из красных. Следовательно, в искомую пару синие гири не входят - значит, входят обе непомеченные. В итоге набирается 10 пар, каждая из которых весит ровно 100 грамм.

[Юляша]

Доказательство для случая гирь с повторяющейся массой, при условии, что 50-граммовых гирь не более двух.

1. Разобьем гири на две группы: гири с массой менее 50 г и гири с массой более 50 г. Если имеются гири с массой ровно 50 г, то кладем одну гирю в одну группу, а другую - в другую.

2. В каждой группе у нас ровно десять гирь (если их больше, то соответствующая группа не удовлетворяет условию).

3. Для каждой гири в другой группе имеется гиря, дополняющая выбранную до 100 г (для доказательства выберем в дополнение к данной всю другую группу гирь).

4. Из каждой группы гирь одинаковой массы, выберем ту, в которой не меньше гирь, чем в группе дополняющих ее до 100 г. В итоге будет отобрано 10 или более гирь.

5. Отобранные гири не удовлетворяют условию, значит их не более 10.

6. Но 10 гирь будет только в том случае, если количество гирь определенной массы и количество гирь, дополняющих их до 100 г, одинаково.

7. Следовательно, гири можно разбить на пары, так что суммарный вес каждой пары - 100 г.

8. Суммарный вес гирь - 1 кг, что и требовалось доказать.

[Dendr]

А вот такая задача...
Для школьников условие было более развернутое, но из него прямо-таки сразу сквозил ответ. Поэтому сокращу его до двух слов:

Который час?

[Юляша]

4:50:00

Который час? Седьмой, осьмой, девятый. - Неправда.