Задача про стопку монет


Оглавление (нажмите, чтобы открыть):

Загадка про фальшивые монеты

07.09.2013, 14:12

Сколько существует вариантов что 3 монеты фальшивые
В кошельке 8 монет из них 5 фальшивые. Вытащили 5 монет. Сколько существует вариантов, что 3 из них.

задача про монеты
на столе лежат n-1 монет.двое игроков по очереди берут по 1,3 или 5 момент за раз.выигрывает тот.

Задача про монеты
Привет. Задача: По кругу расположено N монет гербами вверх и M монет гербами вниз. Обходя круг по.

задача про монеты
Трое поочередно бросают монету. Выигрывает тот, у кого раньше появится герб. Определить вероятность.

Задачка про монеты в кармане
в правом кармане 4 монеты по 20 копеек и 3 по 3 копейки, а в левом 6 по 20 копеек и 3 по 3 копейки.

Задача про 2 монеты

Сегодня предлагаем вам решить несложную задачку, чтобы размять мозги. Условие задачи такое: «У меня в кармане две монеты. В сумме они составляют 15 рублей. Одна из моих монет не 5 рублей. Какие две монеты у меня в камане?»

Сначала постарайтесь решить задачу самостоятельно и напишите свой ответ в комментариях. Затем проверьте себя, посмотрев наше решение.

Довольно известная логическая задача, на которую люди «попадаются» из-за невнимательности. В условии сказано, что одна из монет не 5 рублей. Но из этого не следует, что и вторая монета тоже не 5 рублей. Таким образом, имеем две монеты: 10 рублей и 5 рублей. Что в сумме даёт — 15 рублей.

Задачи на логику, головоломки, загадки, ребусы — Л О Г О — Р А Й

Задачи на логику, алгоритмы, комбинаторика, принцип Дирихле, вероятности, вычисления, математика, геометрия, физика, история, анаграммы, ребусы, шарады

Восемь монет

Над этой хитрой задачкой будут долго думать твои друзья. Если знать секрет, все очень просто, но найти правильное решение без подсказки действительно трудно. Но тебе, возможно, повезет — попробуй решить задачу самостоятельно, прежде чем посмотришь ответ.

Нужно положить восемь монет на стол в один ряд, вот так:

За один ход ты берешь одну монету, переносишь ее через две соседние монеты (монеты, а не стопки!) и кладешь на третью.


За четыре хода должны получиться четыре стопки по две монеты в каждой.

Секрет здесь в том, что надо начинать с монеты №4 — положить ее на №7, или же с монеты №5 — положить ее на монету №2. Дальше все довольно просто — попробуй, и увидишь.

Вот полное решение — №4 на №7, №6 на №2, №1 на №3 и №5 на №8.

Логическая задача. Монеты.

В темной комнате на столе лежит 100 монет. Двадцать из них лежат решкой вверх. Монеты абсолютно одинаковые, и на ощупь определить сторону монеты нельзя. Как разделить монеты на две части, чтобы в каждой получилось одинаковое количество монет, лежащих решкой вверх.

Откладываем двадцать любых монет. Переворачиваем отложенные монеты. В результате количество решек будет одинаковым в обеих частях.
Математическое обоснование:
Делим монеты на две части — левая(80 шт) и правая(20 шт),
Пр — правые решки,
По — правые орлы,
Лр — левые решки,
Ло — левые орлы.
Лр+Ло=80 — восемьдесят монет оставшихся в левой части,
Ло+По=80 — изначально у нас было восемьдесят орлов,
объединяем — Лр+Ло=Ло+По, Ло сокращается и мы получаем
Лр=По — количество левых решек равно количеству правых орлов, а после переворота всех правых монет количество решек в левой и правой части станет равным.

Задача про сто монеток и десять орлов

Постановка задачи

«Месяц назад» (16 июня) в личку на сайте мне пришла замечательная задача от одного из посетителей. Обстоятельства, как это не редко бывает, сложились так, что времени на оформление решения долго не было. Итак:

Примечание

Глава 0 не содержит решения поставленной задачи, но может быть полезна для общего кругозора.

Глава 0. Поворот не туда

Монетки лежат рандомно, оценить состояние («орёл»-«решка») нельзя, известна только статистика «90 к 10». Моя болезненная тяга к теорверу, построила в голове вероятностную модель и увела решение не в то русло.

Сначала мне не понравилось неравномерное распределение. Ну, тут я додумался, что никто не запрещал подбрасывать монетки, инициализируя их состояние заново. Таким образом, мы можем перейти от распределения «9 к 1» к «1 к 1». Тем не менее, всегда остаётся вероятность разделить всю совокупность монет неудачно (и это ещё не принимая во внимание отсутствие гарантии получить равномерное распределение).

Потом были блуждания о выделении нескольких групп: например, при разбиении на 11 групп, в одной гарантированно не будет «орлов». К возможным операциям добавилось инвертирование: монетку можно перевернуть изменив прежнее состояние на противоположное.

С другой стороны, можно понадеяться, что распределение будет сохраняться в больших группах, то есть выборки в 50% объёма генеральной совокупности будут репрезентативны.


В этом случае, количество «орлов» в каждой половине будет почти одинаково. Я взял да и проверил, путём моделирования, среднюю ошибку такого алгоритма. Вот тут-то всё и началось: средний результат сходился совсем не к нулю (как можно подумать сперва), и не к пяти (как можно подумать после первых прикидок). Таким образом, из одной непонятной задачи я синтезировал ещё одну — успех!

Я некоторое время помаялся, потом собрался с мыслями и вспомнил задачу про места в автобусе и гипергеометрическое распределение (не самые весёлые времена, впрочем — это другая история):

Выше приведена формула, позволяющая вычислить вероятность получить в выборке из n элементов k с признаком, если генеральная совокупность состоит из N элементов, среди которых D обладают признаком. Формула очевидна: биномиальный коэффициент в знаменателе определяет количество возможных различных исходов (сочетаний — то есть наборов, отличающихся только составом, но не порядком следования элементов). Числитель — описывает количество комбинаций элементов с признаком, для каждой из которых существует некоторое количество (описываемое вторым сомножителем) комбинаций элементов без признака.

Мастер Йода рекомендует:  Курс «Мобильная разработка»

Если в первую группу попало X1=X монеток с признаком («орлы»), то во вторую попадёт X2=(10-X). Ошибка, в свою очередь:

Дело осталось за малым: посчитать вероятности для всех возможных X, сопоставить каждому X величину Err, после чего вычислить математическое ожидание.

Таблица с вероятностями X, очевидно, будет симметрична:

X p
0,000593419672585812
1 0,00723682527543666
2 0,0379933326960434
3 0,113096432211476
4 0,211413217031676
5 0,259333546225529
6 0,211413217031679
7 0,113096432211476
8 0,0379933326960434
9 0,00723682527543676
10 0,000593419672585804

таблица для Err от X — тоже:

X Err
10
1 8
2 6
3 4
4 2
5
6 2
7 4
8 6
9 8
10 10

— при вычислении вручную, можно прибегнуть к оптимизации.

Как видно — максимум вероятности соответствует X=5 (это интуитивно). Этому же X соответствует нулевая ошибка. Тем не менее, присутствие модуля в выражении Err от X, и сложная зависимость p от X порождает интересную «суперпозицию»: модуль переместит оцениваемое среднее из 0 в отрезок [0;10], а непропорциональное нарастание p сместит среднее от середины отрезка ближе к нулю.

Я набросал решение для MATLAB и промоделировал ситуации с различным количеством «орлов».

Логическая задача про монеты

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

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

Условия задачи

Перед нами 10 пронумерованных мешков, в каждом из которых находится по 10 золотых монет. Каждая монета весит 10 граммов.

В одном из мешков находятся фальшивые монеты. По виду они ничем не отличаются от настоящих, вот только весят они не по 10, а по 11 граммов.

Суть этой логической задачи заключается в том, чтобы при помощи весов найти мешок с фальшивыми монетами. Монеты из мешков можно сколько угодно вынимать и как угодно перекладывать. Казалось бы, дело за малым.


Но вот главное условие, которое делает задачу довольно сложной: взвешивание можно произвести только один раз.

Напомним, что данная головоломка предполагает абсолютно точное решение, поэтому не тратьте время на поиск какого-то подвоха – его тут просто нет. Решается задача исключительно при помощи логического мышления.

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

Что же, удачи вам, и пожалуйста, не ищите готовые ответы или подсказки – используйте свои собственные способности! Наш мозг и так очень мало напрягается в современном мире, так почему бы не использовать редкую возможность размять его при помощи этой великолепной логической задачи?!

Задача Про Стопку Монет

Sascha

Заместитель Администратора

Если вы получили бы стопку монет достоинством в один пенс каждая и высотой с Эмпайр-стейт-билдинг, поместились бы все эти деньги в одном помещении?

Сперва может показаться, что это одна из тех головоломок, задаваемых на собеседованиях, в которых предполагается оценить какое-то абсурдное число. Но на самом деле это не так. Ведь в вопросе спрашивается, поместилось ли это количество монет в помещении? Поэтому ответом на этот вопрос будет «да» или «нет». Разумеется, с объяснением.

Давайте оценим высоту Эмпайр-стейт-билдинг. В здании примерно 100 этажей, значит его высота где-то в 100 раз больше высоты обычной комнаты. Разделим нашу стопку монет на сто меньших стопок высотой от пола до потолка помещения. Теперь перед нами стоит другой вопрос: сможем ли мы разместить примерно 100 стопок монет высотой от пола до потолка в помещении? Легко! Это всего лишь решетка монет десять на десять. В самой крошечной квартире и даже в телефонной будке найдется место, чтобы положить рядом друг с другом сто монет.

Другие задачи на оценку смотрите в нашей

Решение задач на определение фальшивой монеты взвешиванием 2.0

Сегодня я снова хочу вернуться к теме о задаче нахождении фальшивой монеты методом взвешивания на весах без циферблата.

Наиболее распространенные из таких задач — определение количества взвешиваний для выявления фальшивой монеты, если:

1) неизвестно какая она по весу;
2) известно, что она легче/тяжелее остальных.

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


1. Давайте сначала разберемся с 2 вариантом, который является частным случаем варианта 1.

Некоторое время назад, я на Хабре уже описывал решение такой задачи, но в одном из комментариев было замечание о немного странном первом разделении монет, по-этому предлагаю другой алгоритм решения. Хотя результат будет тот же и формула решения задачи остается та же:

N >= log3A,

где N — максимально необходимое количество взвешиваний, натуральное число, округленное в большую сторону;
A — количество монет.
Которая выведена на основании опытов (за 1 взвешивание можно найти одну фальшивую из 3-х монет, за 2 — из 9, за 3 — из 27 и т.д.)

Сам алгоритм решения простой, и я покажу его на примерах

1) Пусть у нас есть 26 монет. Нужно найти одну, которая легче/тяжелее

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

A = 2 * B + C,

где A — количество монет;
B — частное от деления количества монет на 3, натуральное число, округленное в большую сторону;
C — остаток.

По условию задачи

При первом взвешивании будут сравниваться две группы: правая (ПГ) — 9 монет и левая (ЛГ) — 9 монет.

Далее у нас возможны два варианта:

1) фальшивая монета в левой/правой группе (9 монет)
2) фальшивая монета в остатке (8 монет)

для 1 варианта следующее деление на группы будет — 9 = 2 * 3 + 3;
для 2 варианта — 8 = 2 * 3 + 2

Ну и за одно взвешивание можно определить какая из 2 или 3 монет легче/тяжелее

Этот же результат я приведу в таблице

№ взвешивания Число монет ЛГ ПГ Остаток
1 26 9 9 8
2 8 3 3 2
2 9 3 3 3
3 2 1 1
3 3 1 1 1

по формуле — log326 =2.9656 — соответственно количество взвешиваний — 3.


еще пример:
число монет- 71. По формуле log371 =3.8800 — количество взвешиваний — 4. Проверяем

№ взвешивания Число монет ЛГ ПГ Остаток
1 71 24 24 23
2 23 8 8 7
2 24 8 8 8
3 7 3 3 1
3 8 3 3 2
4 2 1 1
4 3 1 1 1

Ну с алгоритм решения этих задач, я думаю, понятен.

2. Теперь перейдем к задачам, в которых не известно легче монета или тяжелее.

В данном случае я предлагаю такое первое действие: разделить монеты на четыре группы, три — с максимально одинаковым количеством монет, а в четвертой группе — остаток. Причем в остатке должны быть 1 или 2 монеты. То есть при делении на 3 частное округляется до меньшего натурального числа.

A = 3 * B + C,

где A — количество монет;
B — частное от деления количества монет на 3, натуральное число, округленное в меньшую сторону;
C — остаток.

Например, для 58-ми монет — это будет 58 = 3 * 19 + 1, для 23 = 3 * 7 + 2, для 15 = 3 * 5 + 0 и т. д.

Мастер Йода рекомендует:  9 плагинов WordPress для оптимизации изображений

Далее выполняем два взвешивания:
1) первая и вторая группы;
2) первая и третья группы;
и анализируем результат.
Здесь возможны четыре варианта:1, 2, 3 — это первая, вторая или третья группа отличаются по весу от двух остальных, или они равны, тогда нам повезло, так как фальшивая — в остатке. Так же два взвешивания помогают определить определить тяжелее фальшивая монета или легче. Кстати, если в остатке две монеты, то нужно выполнить еще 2 взвешивания для определения фальшивой монеты.

Теперь у нас есть задача: определить одну фальшивую монету из группы, которая легче/тяжелее.
Что касается формулы, то она примет следующий вид

N >= log3B + 2,

где N — максимально необходимое количество взвешиваний, натуральное число;
B — количество монет в группе после второго взвешивания.
А если учесть, что B = A/3, где A — количество всех монет, тогда получим:

log3B = log3A — 1,
N >= log3A + 1

1) если известно, что фальшивая монета легче/тяжелее, тогда максимальное число взвешиваний определяется по формуле:

N >= log3A


2) если не известно, какая фальшивая, тогда максимальное число взвешиваний определяется по формуле:

N >= log3A + 1

где N — максимально необходимое количество взвешиваний, натуральное число, округленное в большую сторону;
А — количество монет.

Читают сейчас

Похожие публикации

  • 2 октября 2020 в 11:04

Думай как программист. Урок по решению задач

Тройка, семерка, джокер — разбор решения задач из буклета Gr > +21 6,8k 25 19

Решение задачи замощения с помощью SAT солвера на примере пентамино

Вакансии

AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Комментарии 42

Кстати, если в остатке две монеты, то нужно выполнить еще 2 взвешивания для определения фальшивой монеты.

Вот еще интересная задачка: есть семь мешков с монетами, много монет в каждом мешке, но количество необязательно равное. В одном мешке монеты фальшивые. Вес настоящей монеты 5 грамм, фальшивой — 4. За сколько взвешиваний можно определить мешок с фальшивками, если имеются в распоряжении весы (не две чаши, а электронные весы, показывающие граммы).


Но самая интересная задача, которая мне попадалась — это про цвета глаз жителей племени на необитаемом острове.

Нет, там нужно только одно взвешивание.

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

Например, для 12 монет, замаркированных так, как показано в таблице, нужно проделать такие три взвешивания: (1,4,7,10) – (3,6,9,12), (3,6,9,10) – (2,5,8,12), (3,4,8,12) – (2,6,7,11).

Ваша оценка для первого случая верна, а для второго — нет.

Давайте воспользуемся информационным подходом: в первом случае (когда известно, тяжелее монета или легче) у нас есть A случаев, а каждое взвешивание может дать три исхода (больше, меньше и равно) и в лучшем случае должно уменьшать количество случаев в 3 раза, поэтому, действительно

Если нам неизвестно, тяжелее фальшивая монета или легче, у нас 2A случаев, и оценка должна быть порядка

Что меньше, чем ваша оценка «сверху».

Прежде чем приводить алгоритм, можно ещё улучшить оценку: представим себе, что мы провели все взвешивания, и весы всё время оказывались в равновесии. Даже если в этом случае мы сможем определить фальшивую монету, мы не сможем сказать, тяжелее она или легче (а в задаче это в общем-то и не спрашивается). Таким образом, два случая «сливаются» в один и мы можем, вообще говоря, определить фальшивую за взвешиваний. Однако, это можно сделать только в одном случае: если у нас в кармане есть заведомо настоящая монета.

Утверждение 1: если у нас в кармане есть заведомо настоящая монета, то мы можем определить за n взвешиваний фальшивую среди монет.

Доказательство проведём по индукции. База для n=1. За одно взвешивание мы можем определить фальшивую среди монет. Мы достаём монету из кармана и кладём на одну из чаш весов, а на вторую чашу кладём одну из двух монет среди которых нам нужно определить фальшивку. Если весы в равновесии, то фальшивая монета не участвовала во взвешивании, если не в равновесии — фальшивая та, что на чаше весов.

Допустим, утверждение 1 справедливо для n. Докажем, что за n+1 взвешивание мы сможем определить фальшивую среди монет. Заметим, что если мы добавим к тестовым монетам нашу монету из кармана, то их количество поделится на три:

Тогда разделим наши монеты на три равные кучки, две кучки положим на чаши весов, одну отложим в сторону. Также убедимся, что монета из кармана попала на правую чашу (а не осталась в стороне). Проведём взвешивание. Если оказалось, что весы в равновесии, то фальшивая монета среди отложенных, и за n взвешиваний мы умеем её находить. Если оказалось, что весы не в равновесии, то мы делаем следующий трюк: склеиваем монеты попарно с правой и левой чаш весов. У нас должно получиться «толстых» монет. Среди этих «толстых» монет за n взвешиваний мы умеем определять фальшивую (теперь у нас нет монетки из кармана: она склеена, но мы можем изготовить новую «толстую» монету, склеив две настоящие монеты из кучки, отложенной на первом взвешивании). Единственно, за чем нужно следить, чтобы теперь «толстая» монета, «внутри» которой есть монета из кармана, всегда попадала в откладываемую стопку в последующих взвешиваниях.

Когда мы определили, какая из «толстых» монет фальшивая, мы также определили легче она или тяжелее настоящей. Теперь можно вспомнить результат первого взвешивания: если в первом взвешивании перевесила правая чаша, а фальшивая монета легче, то из двух монет, входящих в «толстую» монету, фальшивая та, которая пришла с левой чаши весов (напомню, в каждой «толстой» монете одна монета с правой чаши, а другая — с левой). Лишь в одном случае мы не можем определить, легче фальшивая или тяжелее: когда во всех взвешиваниях весы были в равновесии. Но в этом случае мы знаем, что «внутри» всё время откладываемой «толстой» монеты, которая оказалось фальшивой, одна из монет — это монета из кармана, поэтому фальшивая вторая монета. Таким образом, мы доказали базу индукции и шаг индукции.

Утверждение 2: если у нас нет дополнительных монет, то за n взвешиваний мы можем определить фальшивую среди монет (на одну меньше, чем в утверждении 1).

Сначала надо пояснить, почему мы не можем достичь максимальной оценки как в утверждении 1. Если у нас нет дополнительной монеты, то мы не можем разделить монет на три кучки. Если мы на чаши весов положим по монет, то в случае если весы окажутся не в равновесии, нам не хватит n−1 взвешиваний, чтобы различить случаев (а именно столько монет сейчас на чашах весов, и каждая может быть фальшивая). А если мы отложим монет, то оставшееся нечётное количество монет мы не сможем уравновесить.

Если же количество монет на одну меньше, то на две чаши весов положим по монет, а в сторону отложим монет. Если весы в равновесии, то за оставшиеся взвешивания мы сможем (согласно утверждению 1) определить фальшивую в отложенных монетах (роль монеты из кармана может играть любая монета с уравновешенных весов). Если весы не в равновесии, то мы также склеиваем монетки как в доказательстве утверждения 1 и добавляем виртуальную монету, которая во всех последующих взвешиваниях будет откладываться.


Задача про стопку монет

не понял в чем соль задачи
если монеты можно трогать .

мне очень нравится задача про «12 монет» и взвешивание на весах — не знаю ни одного человека, кто смог бы решить, не заглянув за решением в интернет)) я честно пару месяцев думал

ну про «трогать» и тем более «определять на ощупь» ничего в условии нет. Речь идет только о том, что их можно переворачивать.

А задачку про 12 монет можете здесь изложить подробно?

не очевидные условия в задаче про 50 монет .

Даны 12 монет, одна из которых фальшивая. Фальшивая монета отличается от остальных по весу, остальные весят одинаково. Причем мы НЕ знаем тяжелее или легче фальшивая монета.

Требуется за 3 взвешивания на аптекарских весах с 2 чашечками и без использования гирь определить, какая из монет фальшивая.

Интересные задачи про монеты

Кто знает, прошу постить задачи, подобные следующим:
Задача №1. Есть 12 монет, среди которых 1 фальшивая. При этом не известно, тажелее она или легче. С помощью чашечных весов (которые показывают «больше» или «меньше») за 3 взвешивания нужно определить фальшивую монету и определить, тяжелее она или легче.
Задача №2. Есть 10 мешочков золота, в каждом мешочке по 10 монет. В одном мешке полностью фальшивое золото. Известно, что вес настоящей монеты 1г, фальшивой — 1,5г. С помощью одночашечных весов, которые показывают точный вес, за 1 взвешивание нужно определить, в каком мешке фальшивое золото.

Задача №3. Есть 10 мешочков золота, в каждом мешочке большое число монет (больше миллиона). В произвольном числе мешков из этих 10-ти полностью фальшивое золото. Известно, что вес настоящей монеты 10г, а фальшивой — 9г. С помощью одночашечных весов, которые показывают точный вес, за 1 взвешивание нужно определить, в каких мешках фальшивое золото.

Вот в такую бутылочку положили монету и заткнули пробкой.
Нужно её достать, вытаскивать пробку и разбивать бутылку нельзя.
=)

Вот в такую бутылочку положили монету и заткнули пробкой.
Нужно её достать, вытаскивать пробку и разбивать бутылку нельзя.
=)

Прорезать отверстие в пробке, она же из пробкового дерева !
Тогда и бутылка не будет разбита и пробка не будет вытащена.

Не получится — бутылка из толстого стекла — стеклорез не поможет.

То же самое, что моя Задача №2


Тут подвох или задача решается честно? Похоже, что вдавить пробку внутрь нужно, нет?
Было бы лучше, если бы на каждый пост(задачу) было бы обсуждение.

Вот только что придумал задачу про монету.
У вас имеется такой стакан:

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

Да, вдавить пробку внутрь.
Слишком лёгкая

выбросить монетку из стакана, не переворачивая его

В воздухе дёрнуть стакан вниз, и отвести его в сторону =)

Держа стакан в одной руке совершить резкое движение рукой вверх,
затем также резко остановить руку. Монетка вылетит из стакана.

совершить резкое движение рукой вверх,
затем также резко остановить руку

Задача №2. Есть 10 мешочков золота, в каждом мешочке по 10 монет. В одном мешке полностью фальшивое золото. Известно, что вес настоящей монеты 1г, фальшивой — 1,5г. С помощью одночашечных весов, которые показывают точный вес, за 1 взвешивание нужно определить, в каком мешке фальшивое золото.

То же самое, что моя Задача №2

тогда надо брать из k-ого мешочка по 100^(k-1) монет и анализировать вес на наличие в нем девяток в соответствующих рарядах

положить на весы по k-монет из k-ого мешочка, тогда фальшивое золото в мешке с номером n = 2m — 110
(где m — получившийся вес монет)

Задача №1. Есть 12 монет, среди которых 1 фальшивая. При этом не известно, тажелее она или легче. С помощью чашечных весов (которые показывают «больше» или «меньше») за 3 взвешивания нужно определить фальшивую монету и определить, тяжелее она или легче.

вообще там говорилось, что больше миллиона монет, но не обязательно, что больше 10^k
надо взвешивать по двоичным разрядам — получим число w_real. потом потом посчитать w_ideal — сколько было бы без фальшивых монет.
потом w_ideal — w_real, получим единицу в разряде для каждой фальшивой монеты.

Есть еще решение:
Тоже разбиваем на 3 группы по 4.
Случай, когда весы уравнены — тривиальный, а вот когда нет — решение таково:
1. Помечаем 0 — легкий, 1 — тяжелый, 2 — настоящий (3-я кучка)
Т.е. 0000 — 1111 \ отдельно 2222
2. Далее монеты 000 убираем, на их место кладем 111, а на место 111 кладем 222, имеем взвешивание
0111 — 2221, тогда 3 случая:
а) положение весов не изменилось, тогда фальшивая или 0(легкая) или 1(тяжелая) на правой чаше (переложенные 111 все настоящие далее взвешиваем либо 2-0 либо 2-1
б) весы уравновесились — мы обрали фальшивую из 000 и она легче, а из 3-х монет за 1 взвешивание определить тривиально
в) положение весов изменилось => мы переложили 1 тяжелую из 111, последнее 3-е взвешивание все покажет.
Твое решение очень понравилось

Задача N4
Есть 100 монет. Они лежат на столе. Известно, что 10 повернуты вверх орлом, другие решкой. Как с завязанными глазами разделить монеты на 2 кучи (необязательно равные) так, чтобы в них оказалось одинаковое количество орлов?

Это простая задача, но ответ говорить не буду, пусть другие тоже догадаются

Монет может быть 13. Что б не путаться в наборах, как мне пришлось когда я первый раз решал можно заглянуть в интернет:

Отложим в сторону тринадцатую монету, а остальные обозначим следующим образом: FAKE MIND CLOT
Теперь взвешиваем одну четверку против другой (буквы обозначают монеты, входящие в каждую четверку): MA DO — LIKE, ME TO — FIND, FAKE — COIN. Теперь совершенно просто найти фальшивую монету, если она входит в эти двенадцать монет. К примеру, если результаты взвешивания были: слева легче, равно, слева легче, то фальшивой может быть только монета «A», которая легче других.
А что если фальшивой окажется все-таки отложенная нами, тринадцатая монета? Все очень просто: в этом случае при всех трёх взвешиваниях весы будут сбалансированы. К сожалению в этом случае нам не узнать легче или тяжелее тринадцатая монета, но в условии такого требования и не было

Добавить комментарий