Součet a produktová hádanka - Sum and Product Puzzle

The Součet a produktová hádanka, také známý jako Nemožné puzzle protože se zdá, že postačuje informace pro řešení je a logická hádanka. Poprvé byla vydána v roce 1969 autorem Hans Freudenthal,[1][2] a jméno Nemožné puzzle byl vytvořen Martin Gardner.[3] Hádanka je řešitelná, i když ne snadno. Existuje mnoho podobných verzí hlavolamů.

Hádanka

X a Y jsou dvě různá celá čísla větší než 1. Jejich součet není větší než 100 a Y je větší než X. S a P jsou dva matematici (a následně dokonalí logici); S zná součet X + Y a P zná produkt X × Y. S i P znají všechny informace v tomto odstavci.

Dojde k následující konverzaci (oba účastníci mluví pravdu):

  • S říká „P neví X a Y."
  • P říká: „Teď už vím X a Y."
  • S říká: „Nyní také vím X a Y."

Jaké jsou X a Y?

Řešení

Řešení má X a Y jako 4 a 13, přičemž P zpočátku věděl, že produkt je 52 a S věděl, že součet je 17.

Zpočátku P nezná řešení, protože

52 = 4 × 13 = 2 × 26

a S ví, že P nezná řešení, protože všechny možné součty k 17 v rámci omezení produkují podobně nejednoznačné produkty. Každý však může vypracovat řešení odstraněním dalších možností, které následují po prohlášeních druhého, a to je pro čtenáře dostačující k nalezení řešení vzhledem k omezením.

Vysvětlení

Problém je poměrně snadno vyřešen, jakmile budou objasněny pojmy a perspektivy. Jsou zapojeny tři strany, S, P a O. S zná součet X + Y„P zná produkt X · Ya pozorovatel O neví nic jiného než původní prohlášení o problému. Všechny tři strany uchovávají stejné informace, ale interpretují je odlišně. Pak se z toho stane hra informací.

Říkejme rozdělení čísla A do dvou termínů A = B + C 2-split. Není třeba žádné pokročilé znalosti jako Goldbachova domněnka nebo skutečnost, že pro produkt PŘED NAŠÍM LETOPOČTEM takového 2-split, aby byl jedinečný (tj. neexistují žádná další dvě čísla, která také při vynásobení přinesou stejný výsledek). Ale s Goldbachovým dohadem, spolu se skutečností, že P by okamžitě poznal X a Y, kdyby jejich produkt byl semiprime, lze odvodit, že součet x + y nemůže být sudý, protože každé sudé číslo lze zapsat jako součet dvou prvočísel. Produktem těchto dvou čísel by pak byl semiprime.

Krok 1. S (Sue), P (Pete) a O (Otto) vytvářejí tabulky všech produktů, které mohou být vytvořeny ze 2-dílných součtů v rozsahu, tj. Od 5 do 100 (X > 1 a Y> X vyžaduje, abychom začali v 5). Například 11 lze rozdělit na 2 + 9, 3 + 8, 4 + 7 a 5 + 6. Příslušné produkty jsou 18, 24, 28 a 30 a hráči označili ve svých tabulkách zaškrtnutí vedle každého z těchto produktů (tabulka 1). Když jsou hotová, některá čísla nemají žádné zaškrtávací značky, některá mají jednu a některá mají více než jednu.

Krok 2. Sue se nyní dívá na svůj součet a všechny jeho 2-rozdělení. Vidí, že všechny 2-rozdělení mají produkty, které nejsou jedinečné, tj. Existuje odlišná faktorizace, což je 2-rozdělení nějakého jiného možného součtu. Vidí to z tabulky v kroku 1, kde všechny její produkty mají více než jednu značku zaškrtnutí. Uvědomuje si, že kvůli této skutečnosti nebude Pete schopen jednoznačně určit faktory X a Y pohledem na produkt (to by vyžadovalo, aby alespoň jeden z kandidátských produktů měl pouze jednu značku zaškrtnutí). Proto volá: „P to nemůže vědět X a Y“. Když to Pete a Otto uslyší, dostanou informaci, že žádný z produktů spojených se součtem Sue není jedinečný. Procházením možných částek mohou Sue, Pete a Otto jeden po druhém sestavit seznam všech způsobilých částek (tabulka 2). Tabulka obsahuje ty součty, jejichž 2-rozdělení mají produkty, které nejsou jedinečné, tj. Mají více než jednu značku v tabulce 1. Sue, Pete a Otto vytvořili tabulku kandidátských součtů (Sue ji samozřejmě už zná součet, ale je třeba vysledovat Peťovo myšlení).

Krok 3. Vzhledem k novým informacím v tabulce 2 se Pete znovu podívá na svůj produkt. Součty všech možných 2-rozdělení jeho produktu kromě jednoho zmizely z tabulky 2 ve srovnání se všemi čísly mezi 5 a 100, které byly od počátku považovány za součty. Jediný, kdo zůstane, musí být součet dvou skrytých čísel X a Y jehož produkt X · Y ví. Podle součtu a produktu je snadné znát jednotlivá čísla, a tak říká Sue, že „Teď už vím X a Y“. Pete je nyní hotov a opouští hru.

Krok 4. Sue a Otto přepočítají tabulku 1, tentokrát počítají pouze produkty 2-splitů ze součtů, které jsou v tabulce 2, místo ze všech čísel v rozmezí 5 až 100 jako v původní tabulce 1. Tato aktualizovaná tabulka se nazývá Tabulka 1B. Sue se podívá na všechny produkty dvoudílného součtu a zjistí, že se objeví jen jeden z nich přesně jednou v tabulce 1B. To pak musí být produkt, který má Pete, a ona může odvodit dvě čísla z jejich součtu a produktu stejně snadno jako Pete. Tak řekla Otto (Pete už je pryč), že „Teď už vím X a Y“. Sue je nyní také hotový a opouští hru, zůstává pouze Otto.

Krok 5. Z informací v kroku 4 Otto prohledá všechny součty v tabulce 2 při hledání jednoho, z nichž pouze jeden 2-split má jednu značku v tabulce 1B. Požadovaný může mít pouze jednu značku, jinak by to Sue nemohla vědět X a Y s jistotou. Nakonec Otto dospěje k požadované částce, která je shodou okolností jediná s těmito vlastnostmi, díky čemuž je původní problém řešitelný pomocí jedinečného řešení. Ottův úkol je nyní také splněn.

Další řešení

Problém lze zobecnit.[2] Svázaný X + Y ≤ 100 je vybráno spíše záměrně. Pokud je limit X + Y je změněn, počet řešení se může změnit. Pro X + Y <62, neexistuje žádné řešení. To se na první pohled od řešení může zdát neintuitivní X = 4, Y = 13 zapadá do hranice. Ale vyloučením produktů s faktory, které se sčítají k číslům mezi těmito hranicemi, již neexistuje více způsobů faktoringu všech neřešení, což vede k tomu, že informace nepřinesou vůbec žádné řešení problému. Například pokud X = 2, Y = 62, X + Y = 64, X·Y= 124 se neuvažuje, pak zbývá pouze jeden produkt 124, viz. 4, 31, což vede k součtu 35. Pak 35 je vyloučeno, když S prohlásí, že P nemůže znát faktory produktu, což by nebylo, kdyby byla povolena částka 64.

Na druhou stranu, když je limit X + Y ≤ 1685 nebo vyšší, objevuje se druhé řešení X = 4, Y = 61. Od té doby tedy problém není řešitelný v tom smyslu, že již neexistuje jedinečné řešení. Podobně, pokud X + Y ≤ 1970 nebo vyšší se objeví třetí řešení (X = 16, Y = 73). Všechna tato tři řešení obsahují jedno prvočíslo. První řešení bez prvočísla je čtvrté, které se objeví na X + Y ≤ 2522 nebo vyšší s hodnotami X = 16 = 2 · 2 · 2 a Y = 111 = 3·37.

Pokud je podmínka Y > X > 1 se změní na Y > X > 2, pro prahové hodnoty existuje jedinečné řešení X + Y ≤ t pro 124 < t <5045, po kterém existuje několik řešení. U 124 a níže neexistují žádná řešení. Není divu, že prahová hodnota pro řešení vzrostla. Intuitivně byl problémový prostor „rozptýlenější“, když prvočíslo 2 již není k dispozici jako faktor X, což vytváří méně možných produktů X · Y z dané částky A. Když existuje mnoho řešení, tedy pro vyšší t, některá řešení se shodují s řešeními pro původní problém s Y > X > 1, například X = 16, Y = 163.

Pokud je podmínka X + Y ≤ t pro nějaký práh t je vyměněn za X · Y ≤ u místo toho problém změní vzhled. Stává se jednodušší řešit s méně potřebnými výpočty. Přiměřená hodnota pro u mohlo by být u = t·t/ 4 pro odpovídající t na základě největšího součinu dvou faktorů, jejichž součet je t bytost (t/2)·(t/ 2). Nyní má problém jedinečné řešení v rozmezí 47 < t < 60, 71 < t < 80, 107 < t <128 a 131 < t <144 a žádné řešení pod touto hranicí. Výsledky alternativní formulace se neshodují s výsledky původní formulace, ani v počtu řešení, ani v obsahu.

Viz také

Reference

  1. ^ Hans Freudenthal, Nieuw Archief Voor Wiskunde, řada 3, svazek 17, 1969, strana 152
  2. ^ A b Born, A .; Hurkens, C. A. J .; Woeginger, G. J. (2006). „Freudenthalův problém a jeho důsledky (část I)“ (PDF). Bulletin Evropské asociace pro teoretickou informatiku, EATCS. 90: 175–191.
  3. ^ Gardner, Martin (Prosinec 1979), „Matematické hry: Pýcha problémů, včetně té, která je prakticky nemožná“, Scientific American, 241: 22–30, doi:10.1038 / scientificamerican0979-22.

externí odkazy