Сколько всего монет в банке если сообщение о нахождении среди них единственной фальшивой

Обновлено: 04.07.2024

1. Сперва разбиваем все 20 монет на 4 равные части по 5 монет.

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

2. Если нашли фальшивку после первого взвешивания, берем эту часть, и делим по такому принципу: 2, 2 и 1 монета.

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

Таким образом можно найти фальшивку за 2 взвешивания (если она будет изначально) или за 3 взвешивания, если ее не будет при начальном взвешивании в любой из частей.

Обращаем внимание, что для первокурсников бакалавриата, специалитета и магистратуры, поступивших в сентябре 2021 года, изначальный пароль для входа - дата рождения в формате чч.мм.гггг. Например, 01.01.2001

Все заявки обрабатываются в порядке живой очереди в режиме неонлайн в течение суток. Техническая поддержка сайта: 521-242

Если Вы НЕ знаете свой логин/пароль, то в письме на email educa@isu.ru укажите в качестве темы "Не знаю логин/пароль" . В теле письма обязательно укажите свои ФИО и учебное подразделение . Письма без указания этих данных обрабатываться не будут.

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

Другой файл cookie предназначен исключительно для удобства, его обычно называют MOODLEID или аналогичным. Он просто запоминает ваше имя пользователя в браузере. Это означает, что когда вы возвращаетесь на этот сайт, поле имени пользователя на странице входа в систему уже заполнено для вас. Отказ от этого файла cookie безопасен - вам нужно будет просто вводить свое имя пользователя при каждом входе в систему.

Некоторые курсы, возможно, открыты для гостей

Войти с использованием учетной записи:

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

Дано: Решение:

N =32 i = log ₂ N = log ₂ 32=5 (бита)

Дано: Решение:

N =128 I = k * i

k =30 i = log ₂ N = log ₂ 128=7 бит - объем одного символа

I - ? I =30*7=210

Задания к практической работе

Задача 3. Сравните объем информации, содержащиеся в двух письмах. Первое письмо состоит из 50 символов 64 – символьного алфавита, а второе – из 40 символов 32 – символьного алфавита.

Дано: Решение:

N =16 i = log ₂ N = log ₂ 16=4 (бита)

Дано: Решение:

N =1 i = log ₂ N = log ₂ 1=0 (бита)

Дано: Решение:

N ₁ =64 i ₁ = log ₂ N ₁ = log ₂ 64=6 (бит)

I ₁ – I ₂ = ? I ₁ - I ₂ =300-200=100 (бит)

Ответ: в первом письме содержится на 100 бит больше информации, чем во втором письме.

Дано : Решение :

I =1/2 I=k*i

k =512 ( бит )

N= ? N=2 i =2 8 =256 ( сим .)

Ответ: мощность алфавита составляет 256 символов.

Дано : Решение :

i₁=2,5*i₂ (i₂ – четное число , т . к . i₁ – целое число )

т.к. и i ₂ – четное число, то i ₂ = 2 (бита)

i ₁ и i ₂ – целые числа (сим.)

Дано: Решение:

N =32 i = log ₂ N = log ₂ 32=5 (бит)

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

У этой задачи есть несколько разновидностей:
1) определить число взвешиваний для выявления фальшивой монеты (она легче или тяжелее)
2) определить алгоритм взвешивания
3) определение тяжелее или легче фальшивая монета
ну и компоновки разновидностей.

Можно было погуглить, но чем-то она меня зацепила, и после нескольких часов ночного осмысливания результатов удалось получить следующее:

1. Определяем количество взвешиваний

из 3 монет фальшивую можно определить за одно взвешивание (она будет либо одна из взвешиваемых, либо в остатке)
из 9 монет можно определить за 2 взвешивания
из 27 — за 3 взвешивания, и т. д.

если искомое число четное
B = A — 3 (n — 1) + 1

и вторая группа

3) группу B — делим по полам на две группы (левая группа — ЛГ, правая группа ПГ). У нас получится три группы

4) Группы ЛГ, ПГ — взвешиваем и определяем группу с фальшивой монетой (D). Возможны 3 варианта:
а) левая группа (ЛГ) монет на весах тяжелее/легче (D = ЛГ)
б) правая группа (ПГ) монет на весах тяжелее/легче (D = ПГ)
в) группы монет на весах одинаковые, тогда фальшивая монета в остатке (D = C).

5) Для группы, найденной в п.4 повторяем пп 1- 4 (A = D), пока количество монет больше 2 ( A > 2)

6) если осталось 2 монеты, выполняем последнее взвешивание (ЛГ = 1 и ПГ = 1)

7) фальшивая монета найдена.

Рассмотрим для наглядности задачу, пусть она будет с того же сайта: нужно разделить 12 монет за 3 взвешивания, фальшивая монета — легче.
1) количество взвешиваний
log12/log3 = 2.261
n = 3 (ну что же, задача решение имеет)
2) делим на группы
B = 12 — 3 (3 — 1) + 1 = 4
C = 12 — 4 = 8
3) группу B делим пополам:
ЛГ = 2, ПГ = 2, остаток C = 8

4) Взвешиваем ЛГ и ПГ.

Варианты после 2-го взвешивания
а) ЛГ = 3 — с фальшивой монетой (повторяем пп.1-4 для 3-ми монет A=3)
б) ПГ = 3 — с фальшивой монетой (повторяем пп.1-4 для 3-ми монет A=3)
в) остаток (C=2) — с фальшивой монетой. переходим к п. 6)

Ну и 3-е взвешивание — из 2-х или 3-х монет определить фальшивую, причем для 3-х монет правило тоже сработает.

3. Определение тяжелее или легче фальшивая монета

Остался 3-й пункт задачи — определить тяжелее фальшивая монета или легче.
Этому решению будет посвящена отдельная статья (ну я так думаю, что будет).

Ответ: Следует учинить непересекающиеся подмножества таблеток от разных упаковок: взять из первой упаковки одну таблетку, из второй - две, из третьей - четыре, из четвёртой - восемь, из пятой - 16, из шестой - 32, из седьмой - 64, из восьмой - 128. Всё это взвесить. Вычесть из полученного веса идеальный вес (идеальный вес каждой таблетки известен из документации, но можно обойтись и без него - подумайте как). Полученный излишек веса (он уже нормализован за счёт единичного излишка веса каждой таблетки) перевести в двоичный вид (ведь мы сформировали подмножества по двоичному закону). В этом числе номера разрядов, равные единице, и будут показывать номера бракованных упаковок.

3)Среди 101 одинаковых по виду монет одна фальшивая, отличающаяся по весу. Как с помощью чашечных весов без гирь за два взвешивания определить, легче или тяжелее фальшивая монета? Hаходить фальшивую монету не требуется.

Ответ: Взвешиваешь 50 и 50 монет:
1) Равенство:
Беpем оставшуюся монету и ставим ее в левую кучку вместо одной из имеющихся там
1.1 Левая кучка тяжелее => фальшивая монета тяжелее
1.2 Левая кучка легче => фальшивая монета легче
2) Hеpавенство:
Беpем более тяжелую кучку и разбиваем ее на две кучки по 25 монет.
2.1 Вес кучек одинаковый => фальшивая монета легче
2.2 Вес кучек неодинаковый => фальшивая монета тяжелее

4)Как развесить 20 фунтов чая в 10 коробок по 2 фунта в каждой за девять развесов имея только гири на 5 и на 9 фунтов? Используются обычные весы с двумя чашами - как у статуи Правосудия :)

Ответ: 1) Hа одну чашу весов положить гирю в 5 фунтов, на другую гирю в 9 фунтов. Затем уравновесить весы, насыпав 4 фунта чая в чашу с гирей на 5 фунтов.
2) Убрать гири с чаш весов, оставить 4 фунта в одной чаше и уравновесить весы, насыпав во вторую еще 4 фунта.
3) Еще раз отвесить 4 фунта.
4) И еще раз 4 фунта. Таким образом, после четырех взвешиваний в остатке будет тоже 4 фунта.
5-9) Разделить 4 фунта пополам, уравновешивая чаши весов.

5)Эта история случилась давным-давно, еще во времена крестовых походов. Один из рыцарей был захвачен мусульманами в плен и предстал перед их предводителем - султаном Саладином, который объявил, что освободит пленника и его коня, если получит выкуп в 100 тысяч золотых монет. "О, великий Саладин, - обратился тогда к султану рыцарь, у которого за душой не было ни гроша, - ты лишаешь последней надежды. У меня на родине мудрому и находчивому пленнику дается шанс выйти на свободу. Если он решит заданную головоломку, его отпускают на все четыре стороны, если нет - сумма выкупа удваивается!"
"Да будет так, - ответил Саладин, и сам обожавший головоломки. - Слушай же. Тебе дадут двенадцать золотых монет и простые весы с двумя чашками, но без гирь. Одна из монет фальшивая, однако неизвестно, легче она или тяжелее настоящих. Ты должен найти ее всего за три взвешивания. Hе справишься с задачей до утра - пеняй на себя!" А вы смогли бы выкрутиться?

Ответ: Эта задача была блестяще разобрана К. Л. Стонгом в майском номере журнала Scientific American за 1955 год. Одно из ее решений (а их довольно много) связано с троичной системой. Сначала запишите все числа от 1 до 12 в троичной системе. Замените в каждом числе цифру 2 на 0, а 0 на 2 и запишите рядом результат. У вас получится три столбца чисел:
1 001 221
2 002 220
3 010 212
4 011 211
5 012 210
6 020 202
7 021 201
8 022 200
9 100 122
10 101 121
11 102 120
12 110 112
Внимательно изучив эти числа, вы обнаружите все числа, в которых встречаются сочетания 01, 12, 20. Каждой из двенадцати монет поставим в соответствие одно из этих чисел.
При первом взвешивании на левую чашу весов кладем четыре монеты, обозначенные числами, которые начинаются с 0, а на правую чашу весов кладем те четыре монеты, которым соответствуют числа, начинающиеся с 2. Если монеты уравновесят друг друга, вы можете утверждать, что число, которое отвечает фальшивой монете, начинается с 1. Если перевесит левая чашка, то искомое число начинается с 0, а если правая - то с 2.
Взвешивая монеты второй раз, их надо распределять в зависимости от средней цифры. Если в центре стоит 0, монета кладется на левую чашу, если 2 - на правую. Вторая цифра числа, обозначающего фальшивую монету, определяется точно так же, как определялась его первая цифра при первом взвешивании.
Производя последнее взвешивание, вы кладете налево те монеты, которые обозначены числами, оканчивающимися на 0, а монеты, соответствующие числам, имеющим на конце 2, вы кладете на правую чащу весов. Таким образом вы узнаете последнюю цифру нужного вам числа.

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

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

7)Имеется 2N пронумерованных монет, причем: все настоящие монеты весят одинаково, все фальшивые также весят одинаково, фальшивая монета легче настоящей. монеты с номерами от 1 до N настоящие, а монеты с номерами от N+1 до 2N - фальшивые. Из этих двух утверждений судья знает только первое, а эксперт - оба.
Как эксперту за три взвешивания на чашечных весах без гирь убедить судью в справедливости второго утверждения?
a: N=7
b: N=9
Задача "a" предлагалась на одной из Всесоюзных мат. олимпиад в 1970-х годах. С тех пор число N=7 (и в общем случае, N=2^K-1 для K взвешиваний) считалось не улучшаемым. И тем не менее, это не так. Улучшение (задача "b") придумано С. Токаревым в 1997 году.

8)Имеется 100 серебряных монет разных размеров и 101 золотая монета также разных размеров. Если у одной монеты размер больше, чем у другой, то она и больше весит, но это верно только для монет, сделанных из одного и того же металла. Все монеты можно легко упорядочить по размерам на глаз. Отличить золота от серебра можно тоже :-). Как за 8 взвешиваний определить, какая монета из всех 201 штук занимает по весу ровно 101-е место? Все 201 монеты также различны по весу. Весы с двумя чашками, как обычно.

9)Еще известная задача такого уровня: (Возможно это легенда, но очень уж красивая)
Во времена Второй Мировой Войны, Английские ученые подбросили Hемецким ученым, что бы они не решали военные проблемы, а решали головоломки, следующую логическую задачу.
Кладоискатели нашли клад и записку в которой было написано: В этих 20 мешках с золотыми монетами есть один мешок с фальшивыми монетами. Известно, что фальшивая монета в два раза тяжелее настоящей.
Задача: Как при помощи одного взвешивания определить в каком мешке находятся фальшивые монеты?
Примечание. Взвешиванием называется тот момент, когда весы, типа коромысла, станут горизонтально, показывая, что на правой стороне весов и на левой стороне одинаковый вес.
И еще Англичане приделали приписку к задаче, что они потратили 10 тысяч человеко-часов для решения этой задачи.

Ответ: Итак, берем из первого мешка 2 монеты, из второго - 4, из третьего - 6 и т.д. Эту кучу монет бросаем на одну чашу весов, после чего уравновешиваем весы, насыпая на вторую чашу монеты из какого-нибудь одного, например первого мешка.
Если бы все монеты были настоящими, то чаша 1 весила бы 420 у.е. Но там-то у нас 2*х фальшивых монет, поэтому она весит 420+2*х у.е.
Предположим, что мешок 1, которым мы уравновешивали весы, содержит настоящие монеты, тогда количество монет, истраченных на равновесие, будет где-то между 422 и 460. Нам остаётся только найти х: х = (кол-во понадобившихся монет - 420)/2
Если же мешок, монетами из которого мы уравновешиваем весы, оказался фальшивым, то равновесие будет достигнуто где-то на между 211 и 230 монетами. Естественно мы тогда поймём, что что-то здесь не так ;-)

10)Имеется 13 монет, из них ровно одна фальшивая, причем неизвестно, легче она настоящих или тяжелее. Требуется найти эту монету за три взвешивания. Весы - стандартные для задач этого типа: две чашечки без гирь.

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

12)У барона Мюнхгаузена есть 8 внешне одинаковых гирек весом 1 г, 2 г, 3 г, . 8 г. Он помнит, какая из гирек сколько весит, но граф Склероз ему не верит. Сможет ли барон провести одно взвешивание на чашечных весах, в результате которого будет однозначно установлен вес хотя бы одной из гирь? (автор - А. В. Шаповалов)

Ответ: Да. 7+8 = 1+2+3+4+5, остается 6.

13)Среди 2000 внешне неразличимых шариков половина - алюминиевые, весом 10 г каждый, а вторая половина - дюралевые, весом 9.9 г каждый. Требуется выделить две кучки шариков так, чтобы количество шариков в кучках было одинаковым, а массы - разными. Каким наименьшим числом взвешиваний на чашечных весах без гирь это можно сделать? (автор - С. И. Токарев)

Ответ: Два. Делим на кучи (1)666, (2)666, (3)666 и (4)2.
Взвешиваем (1)-(2), (2)-(3). Если в обоих случаях равенство, то оставшиеся 2 шарика разные.

Читайте также: