Преглед за печат
Имате шест монети, някои от тях фалшиви. Можете ли с четири претегляния да определите точно кои са фалшивите [?]
1. Везната <s>мери</s> отчита точно тегло.
2. Всички истински монети имат еднакво тегло. Всички фалшиви - също
3. Знаете точните тегла на една истинска и на една фалшива монета.
//ЕДИТ: везна/кантар/теглилка - както искате го наричайте. Измерва и показва точно тегло.
Това везна ли е или кантар? И освен че мери теглото, показва ли го (на дисплей някакъв или циферблат) или не?
Разделяме на две независими групи по три монети и с по две претегляния откриваме фалшивите по следния начин:
1. Претегляме трите заедно и разбираме колко са фалшивите в тройката.
2. При 1:2 слагаме по една монета от двете страни - и готово.
Явно не използвам подходящите думи, когато обяснявам. Имам предвид везна с едно блюдо - не можем да сравняваме тегла. Само измерва тегло.
<blockquote id="quote"><font size="1" id="quote"><b id="quote">quote:</b id="quote"></font id="quote"><table border="0" id="quote"><tr id="quote"><td class="quote" id="quote"><font size="1" id="quote">Имам предвид везна с едно блюдо - не можем да сравняваме тегла. Само измерва тегло.
<div align="right">Originally posted by Edin_Lud - 14/04/2005 : 12:41:43</div id="right">
</td id="quote"></tr id="quote"></table id="quote"></blockquote id="quote"><font size="2" id="quote"></font id="quote">
Аз за това и зададох въпроса по-горе - реално ти говориш не за везна, а за кантар [:o)]
ако не греша фатално, може 4 претегляния, дори май без да знам теглото предварително. условно приемам, че истинските са по-тежки с тегло х, фалшивите са с у.
Случка 1: 5+1 монети
разделям на две произволни групи и с две претегления намирам, в коя група е фалшивата. остават ми три (две са достатъчни) претегляния за да намеря различна монета сред 3. Done.
Случка 2: 4+2 монети
разделям на две произволни групи и с две претегления им намирам теглото.
$2.1 Двете групи тежат различно, значи в тежката иам 3 истински. остават ми две претегляния да намеря различна монета сред 3 в леката. Done
$2.2 Двете групи тежат еднакво ->> по 2+1 монета имам или 2х+у=А общо тегло на група. Общо всичките тежат 3х+3у=2А, значи 2х+2у=3/2А, теглото което трябва да получа ако прибава към едната група фалшивата от другата. остават ми две претегляния да я намеря сред 3. Done
Случка 3: 3+3 монети
Тегля една и помня теглото, примерно х. Тегля втора:
$3.1 втората е х, щастливец съм понеже ми остават две претегляния да намеря третата х сред 3 монети.
$3.2 втората е у. Знам до тук колко тежат х и колко у и имам две претегляния да разделя 4 оставащи монети (2х+2у). Тегля две произволни, ако са 2х или 2у Done. В противен случай сменям едната и тегля пак след което знам кои две кои са. Done.
Сигурно си прав...ако знаеш предварително колко са фалшивите монети
голяма глупост, вярно [Oops!]
mitkko, ти не знаеш предварително разпределението, така че първото ти претегляне трябва да е едно и също винаги. И след това да разклоняваш алгоритъма.
//Едит: Изпреварихте ме...
Броят на фалшивите монети е равен (масата на всичките-броя на монетите) делено (разликата в масата на фалшива истинска) така че още с първото претегляне митко може да определи колко са фалшивите.
пример да кажем че истинските тежат 1 а фалшивите 2
имаме следното разпределение
1 2 2 1 2 1
сумарна маса 9
9-6/1 = 3 фалшиви (има разлика в зависимост какъв е знака, но нали масите се знаят)
Това е стъпка 1.. :)
В такъв случай теглим всичките 6 и какво имаме:
а.X + b.Y = T , където а - тегло на 1 истинска; b - тегло на 1 фалшива; Т - общо тегло; X - брой истински; Y=6 - X - брой фалшиви;
След преобразувания
Х = ( T - 6.b ) / ( a - b) и намираме разпределението.
И оттук нататък не ми се смятат версиите и тегленията[:I]
Абсолютно - от първото теглене на 6 монети и общото тегло Т, решавам Диофантовото уравнвние а.X + b.Y = T (считам, че герой попаднал в ситуация да е съществено да разполага само с 4 тегления е най-малкото необикновен и има подобни способности) и знам рaзпределението на монетите. От там нататък след като зная и теглото на честна/нечестна монета, не се правя на умен както по-горе, една стъпка от алгоритъма се изчиства, евентуално се модифицира малко, това ще го проверим скоро като нарисувам дървото, и в резултат на това разполагаме с another successful story out of the ashes of despair [Yes!]
евентуално [:D]
<blockquote id="quote"><font size="1" id="quote"><b id="quote">quote:</b id="quote"></font id="quote"><table border="0" id="quote"><tr id="quote"><td class="quote" id="quote"><font size="1" id="quote"> решавам Диофантовото уравнвние а.X + b.Y = T
<div align="right">Originally posted by mitkko - 14/04/2005 : 16:34:52</div id="right">
</td id="quote"></tr id="quote"></table id="quote"></blockquote id="quote"><font size="2" id="quote"></font id="quote">
уравнението не е Диофантово
y=6-x, пише го и в поста на bestman
<blockquote id="quote"><font size="1" id="quote"><b id="quote">quote:</b id="quote"></font id="quote"><table border="0" id="quote"><tr id="quote"><td class="quote" id="quote"><font size="1" id="quote"><blockquote id="quote"><font size="1" id="quote"><b id="quote">quote:</b id="quote"></font id="quote"><table border="0" id="quote"><tr id="quote"><td class="quote" id="quote"><font size="1" id="quote"> решавам Диофантовото уравнвние а.X + b.Y = T
<div align="right">Originally posted by mitkko - 14/04/2005 : 16:34:52</div id="right">
</td id="quote"></tr id="quote"></table id="quote"></blockquote id="quote"><font size="2" id="quote"></font id="quote">
уравнението не е Диофантово
y=6-x, пише го и в поста на bestman
<div align="right">Originally posted by Cvetanov - 14/04/2005 : 16:22:07</div id="right">
</td id="quote"></tr id="quote"></table id="quote"></blockquote id="quote"><font size="2" id="quote"></font id="quote">
прав си. дори не се нуждая от необикновени способности за решаването му. [:P]
<blockquote id="quote"><font size="1" id="quote"><b id="quote">quote:</b id="quote"></font id="quote"><table border="0" id="quote"><tr id="quote"><td class="quote" id="quote"><font size="1" id="quote">
$2.2 Двете групи тежат еднакво ->> по 2+1 монета имам или 2х+у=А общо тегло на група. Общо всичките тежат 3х+3у=2А, значи 2х+2у=3/2А, теглото което трябва да получа ако прибава към едната група фалшивата от другата. остават ми две претегляния да я намеря сред 3. Done</td id="quote"></tr id="quote"></table id="quote"></blockquote id="quote"><font size="2" id="quote"></font id="quote">
Ако си изхабиш първото теглене за да определиш колко са фалшивите, мисля че едно теглене няма да стигне за този вариант (4-2, и ако при първото теглене се падне 2-1).