Две задачки

Имеется 1000 монет, среди них 0, 1 или 2 фальшивые. Известно, что фальшивые монеты имеют одинаковую массу, отличную от массы нефальшивых монет. Можно ли за три взвешивания на чашечных весах без гирь определить, есть ли фальшивые монеты и легче они или тяжелее нормальных? (Количество фальшивых монет определять не надо.)

Да.

А как?

А как?

*режим юриста* А надо было четче задавать вопрос :-D

Ну разделить на 4 по 250

Интуитивно почувствовал за 1.5 секунды при помощи колодцев и нитей. Как спросил - так и ответил %)

Не, ну там не так всё просто, нужно же ещё определить, легче фальшивки или тяжелее.

Как Али-Баба сумеет попасть в пещеру?

Скажет: «Сим-Сим откройся.»

Можно ли за три взвешивания на чашечных весах без гирь определить, есть ли фальшивые монеты и легче они или тяжелее нормальных?

И да и нет. Тут чистый рандом.

начать с литра --- это зачет!

Никакого рандома там быть не может. Наличие фальшивых монет определяется даже за 2 взвешивания. Дальше сложнее.
В гугле есть решение, но я что-то там 4 взвешивания насчитал.

А потом всякие поганые конторки, которые по таким задачкам персонал нанимают, выпускают говно.

Погладь свой баттхерт, это задачки с олимпиады по математике.

Да пофиг откуда они.

Как Али-Баба сумеет попасть в пещеру?

Взорвать у входа бочку с порохом, купленную за 1000 монет из 1 задачи: математика «нинужна» :)

насыпать на чашки весов, очевидно, пока не станет ясно.

Первая решается просто. Разделить монеты поровну, взвесить. Если фальшивых монет нечётное кол-во, будет видно сразу. Для чётного кол-ва перемешиваем, делим и снова взвешиваем. Домашнее задание: доказать, что 3 взвешивания достаточно.

Вторая тоже просто: переводим все выключатели в одно положение. Доказать, что при случайном распределении 10 попыток достаточно.

В общем обе задачи из стохастики, которую я никогда не любил и поэтому доказательства приводить не буду. ;)

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

беру слова обратно, вторая тоже просто решается.

Первая решается просто. Разделить монеты поровну, взвесить. Если фальшивых монет нечётное кол-во, будет видно сразу. Для чётного кол-ва перемешиваем, делим и снова взвешиваем. Домашнее задание: доказать, что 3 взвешивания достаточно.

Это-то понятно. Ты забыл что надо определить легче или тяжелее фальшивые. Решения пока нет. В интернетах есть такое:

можно. Приведём пример взвешиваний, позволяющих ответить на вопрос задачи. Первое взвешивание. Разделим все монеты на кучки A и B по 500 монет в каждой и взвесим их на чашечных весах. Тогда возможны два случая. Если A > B (этот случай полностью эквивалентен случаю A < B, поэтому рассмотрим только один из них), то фальшивых монет либо 1, либо 2. В таком случае разделим каждую кучку на две равные части по 250 монет в каждой (A = A1 + A2, B = B1 + B2). Во втором взвешивании на одну чашку весов положим A1 и B1, а на вторую A2 и B2. Опять же возможно два случая, поскольку случай A1 + B1 > A2 + B2 симметричен случаю A1 + B1 < A2 + B2. Если A1 + B1 > A2 + B2, то если фальшивая монета или фальшивые монеты тяжелее, то она или они из A1, если легче, то из B2, а в A2 и B1 — настоящие монеты. Теперь последним взвешиванием, сравнив B1 и B2, выясним, есть ли в B2 фальшивые монеты. Если есть, то они легче настоящих, если нет, то фальшивые в A1, причём они тяжелее настоящих. Если A1 + B1 = A2 + B2, тогда получаем, что фальшивых монет две, причём либо по одной в A1 и A2 и они тяжелее настоящих, либо по одной в B1 и B2 и они легче настоящих. Оставшимся взвешиванием, разделив A1 с одной фальшивой монетой либо без нее на две части по 125 монет и сравнив, получим, если равенство, то монеты в A1 настоящие, а фальшивые в B и они легче настоящих, иначе фальшивые в A и они тяжелее настоящих. Если A = B, тогда фальшивых монет либо вообще нет, либо 2, причём если они есть, то по одной в A и B. Разделив A и B как и в предыдущем случае, сравним A1 с A2. В случае равенства получаем, что фальшивых монет нет. Если же A1 < A2, тогда разделим A1 на две равные части по 125 монет в каждой и сравним их. Если они окажутся равными, то монеты в них настоящие, а значит, фальшивая в A2 и тяжелее настоящих. Если же они не равны, то фальшивая в A1 и легче настоящих.

Но я вижу там 4 взвешивания.

3 взвешивания: 500 vs 500 и две раза по 250 vs 250.

разделив A1 с одной фальшивой монетой либо без нее на две части по 125 монет и сравнив

Почему, их 3, твои 2 выделеных взвешивания - это разные ветки развития событий

А, таки да. Что-то запутался.

Наличие фальшивых монет определяется даже за 2 взвешивания.

Значит мне не показалось, что одно взвешивание тут лишнее? ;-)

Там ещё нужно определить легче фальшивые, или тяжелее. Выше приводил весьма запутанное решение из гугла.

А, вечно я недочитываю. ;)

Первая решается, ровно за 3, пока ответ не написали, и я не стану. Вторая, кажется, неинтересна.

забавно, а мне другое решение в голову пришло, два раза по 333 vs 333, и одно по 167 vs 167

А вроде, может и не попасть: если барабан запустится после включения 3 переключателей одинаково, дальнейшего гарантированного способа определить 4-й переключатель уже нет.

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

День закончился, пришло время ответов.
На вторую задачу ответ публиковать не буду, скажу лишь что она решается в 5 ходов, при желании нагуглить не сложно.

В первой задаче особое внимание необходимо уделить постановке вопроса:
1) Есть фальшивые монеты или нет?
2) Легче они или тяжелее?
3) Количество монет определять не надо.
4) Монет может быть от 0 до 2.

Решение задачи про 1000 монет:
1) Тривиально разбиваем монеты на две группы по 500 монет. Здесь возможны два варианта: если перевесила одна из групп, то на первый вопрос уже есть ответ, и осталось два взвешивания.
  A) Если точно уже есть фальшивая монета или монеты: 
	2) Разбиваем одну из групп, допустим более тяжелую, на две по 250 монет. Здесь снова возможны два варианта:
		Если одна группа перевесила, Значит монеты или монета тяжелее — и это ответ на второй вопрос.
		Если две группы по 250 монет равны по весу, значит либо монеты две и  они распределились поровну, либо монеты легче.
			3) Третье взвешивание: разбиваем любую из групп в 250 монет на группы в 125 монет, взвешиваем, получаем искомое решение.

  Б) Если, изначально две группы по 500 монет весят одинаково, значит монет или две, или их нет.
	2) Разбиваем любую из групп на две по 250 монет, и если здесь есть фальшивая монета, то она одна, а всего их две.
#EOF

не знаю как первая (лень думать)

а во второй ответ - Али-Бабе оторвёт руки при первом запуске барабана.

Ты почти решил, но не распарсил.

Да, вторая симпатичнее.

1) Переводим «вверх» два переключателя, стоящих по диагонали друг от друга. Теперь на одной из диагоналей переключатели стоят «вверх», на другой — неизвестно.

2) Переводим «вверх» два соседних переключателя. Один из них — тот, который мы переключали на прошлом этапе, другой — нет. Теперь три из переключателей стоят «вверх», а четвёртый, если дверь ещё не открылась — «вниз».

3) Пробуем два переключателя по диагонали. Если один из них стоит «вниз», то переводим его «вверх» и дверь открывается. Если оба стоят «вверх», то переводим один из них «вниз». Теперь два соседних переключателя стоят «вниз», два других — «вверх».

4) Пробуем два соседних переключателя. Если они стоят одинаково, оба «вверх» или оба «вниз», то переключаем их в другое положение, и дверь открывается. Если же один из них «вверх», а другой — «вниз», то, опять-таки переключаем оба. Теперь два переключателя на одной диагонали стоят «вверх», а на другой — «вниз».

5) Переключаем два переключателя по диагонали. Дверь открывается.

А первая тупая. Взвешиваем по 500 монет. Варианты: A) Весы в равновесии. Значит, если фальшивые монеты есть, то их две и они попали в разные кучи — по одной. Делим одну из этих куч на две части по 250 монет и взвешиваем. Если весы снова в равновесии, то фальшивых монет нет. Если не в равновесии — есть. Берём более лёгкую часть, делим на две части по 125 монет, взвешиваем. Если весы в равновесии, то фальшивая монета в эти 250 не попала, значит, она тяжелее. Если не в равновесии — легче.

B) Весы не в равновесии, фальшивые монеты есть, и они все в одной из этих частей. Берём более лёгкую, делим на части по 250 и взвешиваем. Если весы не в равновесии, то в более лёгкой части из 500 монет есть фальшивые. Значит, фальшивые монеты легче. Если в равновесии, то есть два варианта: либо фальшивые монеты тяжелее и попали в другие 500, либо они легче, их две и при втором взвешивании они разделились пополам. Теперь берём одну из этих мелких частей по 250 монет, делим пополам, по 125, и снова взвешиваем. Если весы в равновесии, то это первый вариант и фальшивые монеты тяжелее. Если не в равновесии — то второй, и фальшивые монеты легче.

Упущен вариант с нулём фальшивых монет.

Честно говоря, мне не нравятся такие решения задач, когда предполагается насыпать две кучи монет на одну чашу весов, а после этого точно разобрать их по исходным кучам (как в этой задаче - A1 и B1 собрали на чашу, затем разобрали по исходным A1 и B1), читерство какое-то.

Если их ноль, значит, их нет. Ваш кэп.

Ах, да, невнимательно прочёл, прошу прощения.