Визначити фальшивку з 13 монет за 3 зважування, 1000 задач

Є 13 монет, серед яких одна фальшива. Відомо, що фальшива монета відрізняється від інших вагою, але як саме, легше чи важче, не відомо. Як за допомогою чашкових ваг визначити фальшивку на більш, ніж за три зважування?

Розіб'ємо монети на три групи по 4, 4 і 5. На ваги покладемо перші дві, т. Е. По чотири монети на кожну чашу. Внаслідок такого першого зважування можливі дві ситуації:

1. Ваги врівноважені і обидві групи по 4 монети мають однакову вагу. У цьому випадку нам пощастило, так як ми отримали 8 справжніх монет на вагах, а фальшивка виявилася середовища решти п'яти.
Далі на одну чашу терезів покладемо будь-які три з решти п'яти монет, а на другою - три монети з 8-ми, визначених нами як справжні в першому зважуванні. Тут маємо три можливих результату зважування:

1.1. Три монети, взяті нами з 5-ти досліджуваних, виявилися важче трьох справжніх (взятих з 8-ми перевірених в першому зважуванні). В цьому випадку фальшивка знаходиться серед взятих монет і вона важча справжньою монети.
Беремо ці монети, відкладаємо одну з них в сторону, а дві кладемо на шальки терезів. Якщо шальки терезів врівноважені, то фальшивою виявилася відкладена монета, якщо немає, то та, яка важче з двох, покладених на шальки терезів.

1.2. Три монети, взяті нами з 5-ти досліджуваних, виявилися легше трьох справжніх (взятих з 8-ми перевірених). В цьому випадку фальшивка знаходиться серед взятих монет і вона легше справжньою монети.
Далі, як і в попередньому випадку, відкладаємо одну з трьох монет в сторону, а дві зважуємо. Якщо шальки терезів врівноважені, то це свідчить про те, що ми відклали фальшиву. Якщо монети на вагах мають різну вагу, то та, яка легше і є фальшива.

1.3. Три монети, взяті нами з 5-ти досліджуваних і три справжніх (взятих з 8-ми перевірених) виявилися однакової ваги. В цьому випадку чергові три монети виявилися справжніми, а фальшива залишилася серед двох монет, які ми ще не зважували. Щоб визначити яка з них є фальшивою, для третього зважування візьмемо одну з цих двох монет і будь-яку справжню (з 11-ти перевірених). Якщо ваги врівноважені, то фальшива монета так, яку ми залишили, якщо немає, то та, яку ми поклали на ваги.

2. Ваги після першого зважування не врівноважені і перші групи по 4 монети мають різну вагу. У цьому випадку нам теж пощастило, так як ми знаємо, що фальшива монета знаходиться серед 8-ми монет на вагах, і ми має 5 справжніх монет, які залишилися не на вагах.
Для зручності подальшого викладу, без зменшення спільності, будемо вважати, що ліва чаша терезів виявилася легшою, а права важче (поворот ваг на 180 градусів не можна вважати новим зважуванням) .Проделаем з монетами на вагах наступне:

з лівої чаші знімемо одну монету і відкладемо вліво;
дві монети з правого чаші перекладемо на ліву. Очевидно, що слід запам'ятати які саме монети ми перекладали, наприклад, між іншим їх зверху;
інші дві монети з правого чаші відкладемо в іншу сторону (вправо);
на праву чашу покладемо 5 монет, які не брали участі в першому зважуванні. Ми вже знаємо що вони справжні.

Таким чином отримаємо друге зважування по 5 монет на кожній чаші. Його можливі результати:

2.1. Шальки терезів врівноважені. Тоді всі 10 монет на вагах справжні, а фальшива знаходиться серед трьох відкладених: одна зліва і лівої чаші (яка була легше) і дві праворуч з правої частини (важче). Для третього зважування беремо обидві монети, викладені з правої частини:

2.1.1. Відкладені з правої чаші монети однакової ваги. Отже, фальшивкою виявилася монета, відкладена з лівої чаші.

2.1.2. Відкладені з правої чаші монети різної ваги. Отже, одна з них фальшива, але обидві монети при другому зважуванні були на правій чаші, яка виявилася важче, значить фальшива монета важче інших. В цьому випадку фальшива монета та, яка виявилася на вагах важче при третьому зважуванні.

2.2. При другому зважуванні ліва чаша терезів залишилася легше (як і при першому). Значить фальшива монета залишилася на лівій чаші серед трьох, які ми залишили на ній після першого зважування. Можна стверджувати, що фальшивка легше справжньою монети, так як на правій чаші у нас справжні монети. Беремо три монети які залишалися на лівій чаші при обох зважуваннях. Дві з цих монет кладемо на різні шальки терезів, якщо одна з них легше, то вона фальшива, якщо ж вони однакові, то фальшива монета, що залишилася з цих трьох.

2.3. Нарешті, якщо при другому зважуванні ліва чаша виявилася важче, то, по-перше, фальшивка важче інших, по-друге, ми переклали її з правої чаші (в першому зважуванні права чаша виявилася важче). У цьому випадку досить зважити дві монети, які ми перекладали з правої чаші в ліву після першого зважування. Яка з них виявиться важче - та й є фальшивка.