Úkoly vážení

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 21. února 2017; kontroly vyžadují 36 úprav .

Úlohy na vážení jsou typem olympijských úloh v matematice, ve kterých je třeba zjistit jednu nebo druhou skutečnost (vybrat padělanou minci mezi skutečnými, seřadit sadu závaží ve vzestupném pořadí podle hmotnosti atd.) vážením na váze. stupnice bez číselníku. Jako vážené předměty se nejčastěji používají mince. Méně běžně existuje také sada závaží o známé hmotnosti.

Velmi často se používá prohlášení o problému, které vyžaduje buď určit minimální počet vážení potřebných ke zjištění určité skutečnosti, nebo dát algoritmus pro určení této skutečnosti pro určitý počet vážení.

Méně časté je tvrzení, které vyžaduje odpověď na otázku, zda je možné pro určitý počet vážení zjistit určitou skutečnost. Takové tvrzení často není příliš úspěšné, protože s kladnou odpovědí na otázku se problém nejčastěji týká sestavení algoritmu a záporná odpověď se v praxi olympiád téměř nikdy nenajde.

Při řešení problémů s vážením často dochází k typické chybě: je třeba určit minimální počet vážení. Při řešení je sestaven algoritmus, který umožňuje řešit problém v krocích. Zároveň je to skutečně správná odpověď na otázku „jaký je minimální počet vážení“, ale tato skutečnost nebyla v řešení prokázána . Někdy se této chyby dopouštějí samotní kompilátoři problémů. $m$ $m$

Analýza z hlediska teorie informace

Při řešení těchto problémů se často používá následující úvaha [1] : váhy mohou být v jednom ze tří stavů:

převážil levý pohár;
převážil správný pohár;
poháry jsou v rovnováze.

Jediné vážení nám tedy říká jednu číslici v ternární číselné soustavě a vážení nám umožňuje oddělit pouze různé situace. Tato úvaha je užitečná zejména při prokazování minimalizace potřebného počtu vážení a při prokazování nemožnosti určit určitou skutečnost pro daný počet vážení (v druhém případě je obvykle vyžadována kombinatorická analýza prostoru možných odpovědí ) . $m$ ${\displaystyle 3^{m))$

Příklad: při dvou vážení není možné s určitostí vybrat nejtěžší z 10 kettlebellů, protože dvě vážení umožňují oddělit pouze 9 možných odpovědí a kterýkoli z 10 kettlebellů může být nejtěžší.

Někdy se udělá chyba, když je obecně řečeno správné uvažování, ale „neutrální“ poloha váhy je přehlížena a předpokládá se, že při každém vážení je hlášen jeden ze dvou a ne jeden ze tří možných výsledků.

Problém nalezení jedné padělané mince, jejíž hmotnost může být větší nebo menší než hmotnost správné mince

Z netriviálních problémů s vážením byl studován a dobře znám problém, kdy je třeba určit, zda mezi 12 existuje padělaná mince, a pokud ano, najít ji a určit její relativní váhu. Tento problém a jeho řešení poprvé publikoval v roce 1945 R. L. Goodstein v The Mathematical Gazette (viz článek [2] ). V tomto problému existuje statický algoritmus (tj. algoritmus, ve kterém je vážení předem určeno a nezávisí na výsledcích předchozích vážení), který má najít falešnou minci ve 3 vážení. Tento algoritmus může být reprezentován následující tabulkou:

0 0 1 0 0 2 2 2 1 1 1 2 0 1 0 2 2 2 1 0 0 1 2 1 1 0 0 2 1 0 0 2 2 2 1 1

V tabulce čísla sloupců odpovídají číslům mincí a řádky určují vážení: 0 - mince se neúčastní vážení, 1 - je umístěna na první misku, 2 - je umístěna na druhou misku . V důsledku tří vážení je stanoven tzv. syndrom, tedy trojnásobek čísel, která jednoznačně udávají číslo padělané mince. Toto číslo se rovná číslu sloupce s odpovídajícím syndromem. Pokud je například syndrom (2,2,0), pak má padělaná mince číslo 6 a je těžší než referenční mince.

V jiných verzích podobných problémů může být uvedeno, že je nutné najít padělanou minci mezi 13 (bez určení její relativní hmotnosti), pokud je známo, že ve zkušební skupině je právě jedna padělaná mince. Je zřejmé, že pro takový úkol můžete použít algoritmus již vytvořený výše, když jste předtím odložili jednu minci a učinili závěr o její pravosti na základě výsledků vážení zbývajících 12 mincí.

Poměrně obecný obrázek o počtu mincí n, z nichž jednu nepravou lze nalézt v m vážení, si lze udělat z [3] . Nechť je možné najít falešnou minci z daného počtu mincí v m vážení. Potom maximální možný počet mincí je:

pokud je předem známa relativní hmotnost padělané mince - (bez ohledu na dostupnost zásoby skutečných mincí); ${\displaystyle 3^{m))$

pokud relativní hmotnost není známa a chcete ji znát:

- při nedostatku skutečných mincí - ; $(3^{m}-3)/2$

– pokud je k dispozici – , $(3^{m}-1)/2$

pokud nechcete znát relativní váhu:

- při nedostatku skutečných mincí - ; $(3^{m}-1)/2$

– pokud je k dispozici – . $(3^{m}+1)/2$

Zobecnění

Zobecněný popis problémů tohoto typu je uveden v [4] .

Nechť -- - dimenzionální euklidovský prostor , -- skalární součin vektorů a z Pro prvky a podmnožiny se používají operace a výsledky jejich aplikace jsou určeny vztahy ; , , Symbol bude označovat diskrétní [−1; 1]-kostka v ; tj. množina všech sekvencí délek v abecedě . Množina je diskrétní koule o poloměru (v Hammingově metrice ) se středem v bodě Nechť existují objekty, jejichž relativní váhy jsou dány vektorem , který určuje konfiguraci vah množiny objektů: -tý objekt má standardní váha, pokud je váha -tého objektu větší (menší) o konstantní (neznámou) hodnotu if (respektive ). Vektor charakterizuje typy objektů: standardní, nestandardní (tj. konfigurace typů) a neobsahuje informace o relativních vahách nestandardních objektů. $\mathbb{R}^n$ $n$ $[\mathrm {e} ^{1},\mathrm {e} ^{2}]$ $\mathrm {e} ^{1}$ ${\displaystyle \mathrm {e} ^{2))$ $\mathbb {R} ^{n},$ $\mathrm {e} =(e_{1},\tečky ,e_{n})\in \mathbb {R} ^{n}$ $E=\{\mathrm {e} ^{j}\}\subseteq \mathbb {R} ^{n},$ $(\cdot )^{*}$ ${\displaystyle (\cdot )^{+))$ ${\displaystyle \mathrm {e} ^{*}=(znak(e_{i}))_{i))$ ${\displaystyle E^{*}=\{(\mathrm {e} ^{j})^{*}\))$ ${\displaystyle \mathrm {e} ^{+}=(|sign(e_{i})|)_{i))$ $E^{+}=\{(\mathrm {e} ^{j})^{+}\}.$ $I^{n}$ $\mathbb{R}^n$ $n$ $I=\{-1,0,1\}$ ${\displaystyle I_{t}^{n}=\{\mathrm {x} \in I^{n}|w(\mathrm {x} )\leq t\}\subseteq I^{n))$ $t$ $w()$ $\mathrm {0} .$ $n$ $\mathrm {x} =(x_{1},\tečky ,x_{n})\in I^{n},$ $i$ $x_{i}=0;$ $i$ $x_{i}=1$ $x_{i}=-1$ ${\displaystyle \mathrm {x} ^{+))$

Vážení (kontrola) je dána vektorem a výsledek vážení pro danou situaci je roven vážení, definované vektorem, má následující interpretaci: pro tuto kontrolu se vážení účastní tý předmět, pokud je umístěn vlevo. miska váhy, je- li vpravo - jestliže Při každém vážení na obou kelímcích musí být stejný počet předmětů, chybějící počet předmětů na libovolném kelímku se doplní referenčními předměty, jejichž počet se rovná Výsledek vážení popisuje případy: pro - rovnováhu, pro - levý pohár převažuje, pro - pravý pohár převažuje. Vážení, které nepoužívá další referenční objekty ( ), se nazývá centrované . Neúplnost výchozích informací o rozložení vah uvažované skupiny objektů je charakterizována množinou přípustných rozložení vah objektů, která se také nazývá množina přípustných situací , prvky se nazývají přípustné situace . ${\textbf {h}}\in I^{n},$ ${\textbf {x}}\in I^{n}$ $s({\textbf {x}},{\textbf {h}})=sign([{\textbf {x}},{\textbf {h}}]).$ ${\textbf {h}}=(h_{1},\tečky ,h_{n}),$ $i$ $h_{i}\neq 0;$ $h_{i}<0$ $h_{i}>0.$ ${\textbf {h))$ $r({\textbf {h}})=[{\textbf {h}},{\textbf {1}}].$ $s({\textbf {x)),{\textbf {h)))$ $s({\textbf {x)),{\textbf {h)))=0$ $s({\textbf {x)),{\textbf {h)))=-1$ $s({\textbf {x)),{\textbf {h)))=1$ $r({\textbf {h)))=0$ $Z\subseteq I^{n},$ ${\textbf {z}}\in Z$

Každé vážení určuje rozdělení množiny rovinou na tři části a odpovídající dělení množiny , kde S ohledem na to řekneme, že vážení klasifikuje prvky podle typů odpovídajících podmnožinám , přičemž hodnota se nazývá průměr množiny. klasifikace souboru vážením ${\textbf {h))$ $I^{n}$ $[{\textbf {x}},{\textbf {h}}]=0$ $W(s|I^{n},{\textbf {h)))=\{{\textbf {x}}\in I^{n}|s({\textbf {x)),{ \textbf {h}})=s\},s\in I,$ $Z=W(0|Z,{\textbf {h)))+W(1|Z,{\textbf {h)))+W(-1|Z,{\textbf {h))) ),$ $W(s|Z,{\textbf {h)))=W(s|I^{n},{\textbf {h)))\cap Z.$ ${\textbf {h))$ ${\textbf {z}}\in Z$ $W(s|Z,{\textbf {h)))$ $d(Z,{\textbf {h)))=\max _{s\in I}|W(s|Z,{\textbf {h)))|$ $Z$ ${\textbf {h}).$

Definice 1 . Algoritmus vážení délky je posloupnost , kde je funkce, která určuje kontrolu v každém kroku algoritmu na základě výsledků vážení v předchozích krocích - daná počáteční kontrola). ${\mathcal {A}}$ $m$ ${\mathcal {A} }=\langle \mathrm {A} _{1},\tečky ,\mathrm {A} _{m}\rangle$ $\mathrm {A} _{j}:I^{j-1}\to I^{n}$ ${\textbf {h}}^{j}=\mathrm {A} _{j}({\textbf {s}}^{j-1}),$ ${\textbf {h}^{j}\in I^{n},$ $j$ $,j=1,2,\tečky ,m,$ ${\textbf {s}}^{j-1}=(s_{1},\tečky ,s_{j-1})\in I^{j-1}$ $({\textbf {h}}^{1}=\mathrm {A} _{1}()$

Nechť je množina všech -syndromů, množina situací, které mají stejný syndrom , tzn. $S(Z{\mathcal {A}})$ $(Z,{\mathcal {A}})$ $W({\textbf {s}}|{\mathcal {A}})\subseteq I^{n}$ ${\textbf {s)),$ $W({\textbf {s}}|{\mathcal {A}})=\{{\textbf {z}}\in I^{n}|{\textbf {s}}({\textbf {z}}|{\mathcal {A}})={\textbf {s}}\};$ $W({\textbf {s}}|Z,{\mathcal {A}})=W({\textbf {s}}|{\mathcal {A}})\cap Z.$

Definice 2. AB se nazývá ${\mathcal {A}}$

a) identifikace situací v souboru , pokud je podmínka splněna pro všechny $Z$ ${{\textbf {s}}\in S(Z,{\mathcal {A))))$ $|W({\textbf {s}}|Z,{\mathcal {A}})|=1;$

b) identifikace typů objektů v množině , pokud je podmínka splněna u všech $Z$ ${\textbf {s}}\in S(Z,{\mathcal {A}})$ $|W^{+}({\textbf {s}}|Z,{\mathcal {A}})|=1.$

V [4] bylo prokázáno , že pro danou třídu množin (nazývané vhodné množiny) algoritmus, který identifikuje typy objektů, také identifikuje situace v . $Z$ $Z$

Jako příklad jsou konstruovány dynamické (dvoufázové) váhové algoritmy s parametry = 11, = 5, = 2, které odpovídají parametrům dokonalého Golayova kódu (Virtakallio-Golay kód). $n$ $m$ $t$

Každý z sestrojených algoritmů pro 5 vážení najde z 11 testovaných mincí až dvě falešné, jejichž hmotnosti mohou být o pevně stanovenou částku větší nebo menší než váha skutečné mince. V tomto případě doména neurčitosti obsahuje situace, tj. sestrojený AB leží na Hammingově horní hranici a je v tomto smyslu dokonalý (viz ternární Golayův kód ). Zároveň bylo zjištěno, že neexistuje statický AB (vážící kód) s parametry = 11, = 5, = 2. ${\displaystyle 1+2C_{11}^{1}+2^{2}C_{11}^{2}=3^{5))$ $n$ $m$ $t$

V současné době není známo, zda existují další dokonalé AB, které identifikují situace pro jakékoli hodnoty . Navíc není známo, zda pro nějaké řešení rovnice existuje odpovídající Hammingova vazba pro ternární kódy, což je zjevně nutné pro existenci dokonalého AB. Je známo pouze to, že pro dokonalý AB neexistuje žádný AB a pro , má tato rovnice jedinečné netriviální řešení, které určuje parametry sestrojeného dokonalého AB. ${\displaystyle I_{t}^{n))$ $t$ $t>2$ $\sum _{i=0}^{t}2^{i}C_{n}^{i}=3^{m},$ $t=1$ $t=2$ $n,m,t$

"Nestandardní" problémy s vážením

Někdy existují „nestandardní“ úlohy vážení, například:

jejich součástí jsou váhy, které přímo ukazují hmotnost
mají pákové váhy s číselníkem ukazujícím rozdíl v hmotnosti závaží na miskách
objevuje se v nich ocelárna
mají nestejná měřítka

S takovým problémem přišel K. Knop. Máme n mincí, z nichž jedna je padělaná (není známa větší ani menší váha než skutečné mince, které mají stejnou váhu). K dispozici jsou 2 můstky, které lze používat paralelně. Každé vážení trvá minutu. Jaký je maximální počet mincí n, mezi kterými můžete najít padělanou minci za 5 minut? [5]

Poznámky

↑ Yaglom A.M., Yaglom I.M. Pravděpodobnost a informace. M.: Nauka, Moskva, 1973
↑ Shestopal G. Jak odhalit falešnou minci. Kvant, 1979, č. 10. str. 21-25.
↑ Kanel-Belov, A.Ya.; Frenkin, B. R. Dodatek k článku D. A. Mikhalina, I. M. Nikonova „Jeden problém nalezení padělané mince“ // Matematické vzdělávání: časopis. - 2007. - T. 11 . - S. 149-158 . (Ruština)
↑ 1 2 Chudnov A. M. „Algoritmy pro klasifikaci a identifikaci situací na základě vážení“, Diskr. Mat., 26:4 (2014), 119–134, DOI: https://doi.org/10.4213/dm1310 (ruština); Diskrétní matematika. Aplikace 25:2 (2015), 69–81. https://doi.org/10.1515/dma-2015-0007(eng ).
↑ http://arxiv.org/pdf/1310.7268.pdf Archivováno 16. srpna 2017 na Wayback Machine Řešení problému padělaných mincí a jeho zobecnění