Od 1 do 100
Mám ještě jednu krásnou matematickou úlohu.
Alice a Bob hrají hru.
Alice vybere 10 různých čísel od 1 do 100.
Pokud Bob dokáže najít v těchto deseti číslech dvě podmnožiny čísel bez společných prvků tak, aby jejich součty byly stejné, vyhraje.
Příklad:
Alice vybrala [1 3 5 7 9 11 13 15 17 19]
Bob našel [7+9]=16 a [1+15]=16 a vyhrál
Otázka: jakou skupinu čísel byste poradili Alici vy?
Tomáš B.
31. 03. 2016 13:34
12 odpovědí
Dobrý den,
na 3. pokus jsem zkusil tyto čísla: 17 34 47 42 11 60 78 82 96 12
Pouze jednou jsem zkoušel kontrolu a to tak, že jsem vzal největší číslo a odečítal od nich jedno po druhé ostatní s tím, že výsledek (tedy číslo po odečtení) se nesmí objevit v samé řadě.
Snad to bude dobře.
Ahoj Jirko, to je chytré, ale Bob by na to odpověděl například:
59 = (17+42) = (47+12) 76 = (34+42) = (17+47+12)
A co prvnich deset clenu Fibonaciho posloupnosti .. ty by meli fungovat .
{ 1,2,3,5,8,13,21,34,55,89}
a nebo
{ 1,10,20,30,50,96,97,98,99,100}
Petře, toho Fibonacciho radši ani nebudu komentovat...
U druhé je hned vidět, že 10+20 = 30, 99+1 = 100
Aha ted jsem teprve pochopil (doufam :) ) zadani.
Ja si myslim ze to nema reseni resp. kazda deseti clena podmnozina cisel 1-100 nesplni ten Bobuv pozadavek. Protoze: zacnu 1 pak muzu rovnou 2 ale 3 uz ne tak tam dam 4 ale 5,6,7 nemuzu a tak tam dam 8 .. atd atd . coz jsou mocniny dvojky a tento vzorec pokracuje .. ale mocnin dvojky mensich nez 100 je pouze sedum a tahle konstrukce je podle me ta nejuspornejsi mozna . takze to podle me nema reseni
Je pravda, že každá super-rostoucí posloupnost (člen je vyšší než součet předchozích členů) bude zadání splňovat a je také pravda, že tady takovou posloupnost nelze vytvořit.
Už ale není pravda, že je to nejúspornější konstrukce.
Když se pro jednoduchost omezím na 4 členy, tak [3 5 6 7] nemá různé podmnožiny se stejným součtem, není super-rostoucí a je úspornější než [1 2 4 8] o jeden prvek.
Pokud řešení neexistuje, chtělo by to dokázat, ale tvoje argumentace není správná.
Ahoj všichni, mám jen dotaz :)
Tomáši? Co má společného 10+20=30 a 99+1=100 se zadáním? :) Protože pak asi úplně nechápu co má Bob najít..nebo vlastně spíš najít nemá :)
Ahoj Pavle,
pro { 1,10,20,30,50,96,97,98,99,100} platí: { 10,20} = { 30} = 30 nebo { 1,99} = { 100} = 100. To jsou hned dvě řešení pro Boba.
Zadání ti můžu zopakovat formálně.
Alice vybere 10ti prvkovou množinu P ⊆ Z[1, 100] a úkolem Boba je najít dvě disjunktní podmnožiny A ⊆ P, B ⊆ P, které budou mít stejný součet svých prvků.
To je dobrá hádanka, ale řekl bych, že je to trošku chyták :D největší možný rozestup mezi 10 čísly od sebe navzájem (ze 100) je 10 a máme vybrat deset čísel. Součet možná půjde vždycky, ale nejsem si jistý ;) jenom jsem si na chvilku zapřemýšlel
Když si to tak čtu, tak to nějak pořád nechápu :D
Na téhle úloze je zajímavé, že při troše znalostí číselných soustav to svádí k exponenciálním posloupnostem: 1, 2, 4, 8, 16, 32, 64 - a dál nemůžeme - takže lze najít nejvýše 7-prvkovou množinu?
Petr například napsal, že je to nejefektivnější konstrukce.
Tenhle typ posloupnosti, který odpovídá dvojkové soustavě se používá proto, že ho lze snadno implementovat v hardwaru.
Je také velice efektivní v reprezentaci celočíselného prostoru a jeho úplného pokrytí.
Rozhodně však není "nejefektivnější" reprezentací, tou je ve skutečnosti trojková soustava, což souvisí s teorií informace a Eulerovým číslem, které je blíže číslu 3.
A je tady problém - zatímco báze na základě mocnin 2 se snaží o minimální množinu pokrývající dískrétní prostor, nás zajímá existence méně efektivní báze, která umožní vznik "děr" - neschopnost reprezentovat některé hodnoty.
U dvojkové soustavy díry nemohou vznikat právě kvůli způsobu konstrukce, což se využívá například v kompresi nebo kryptografii.
Ovšem existují také báze, kterým říkáme nehomogenní.
Příkladem je například naše měna: 1, 2, 5, 10, 100
Ta nemá schopnost úplného pokrytí, což má za následek, že se vám prodavačka omlouvá, když vám vrací nazpět 8 desetikorun.
Další zajímavou bází je faktoriálová soustava: 1, 2, 6, 24, 120, ...
Způsob její konstrukce vytváří více možností "neefektivity".
Důkazem je například posloupnost (1, 2, 12, 24, 48, 92, 96, 100)
To je 8-prvková množina, jejích podmnožiny mají jedinečné součty.
Některé lidi už napadlo, že Alice nemůže vyhrát - a já netvrdím, že může.
Otázkou ale zůstává, proč ne?
Dobře, takže problém můžeme přeformulovat takto: existuje dostatečně blbá(=neefektivní) báze? Pokud se nám podaří ukázat, že ne, tak je hotovo a Alice nemůže vyhrát.