Summa och produktpussel

Summan och produktpusslet , även känt som det omöjliga pusslet eftersom det verkar sakna tillräcklig information för en lösning, är ett logiskt pussel . Den publicerades första gången 1969 av Hans Freudenthal och namnet Impossible Puzzle myntades av Martin Gardner . Pusslet är lösbart, men inte lätt. Det finns många liknande pussel.

Pussel

X och Y är två olika heltal större än 1. Deras summa är inte större än 100. S och P är två matematiker (och följaktligen perfekta logiker); S känner till summan X + Y och P känner till produkten X × Y . Både S och P känner till all information i detta stycke.

I följande konversation talar båda deltagarna alltid sanningen:

  • S säger "P känner inte till X och Y. "
  • P säger "Nu vet jag X och Y. "
  • S säger "Nu känner jag också X och Y. "

Vad är X och Y ?

Förklaring

Problemet är ganska enkelt att lösa när begreppen och perspektiven är tydliga. Det är tre parter inblandade, S, P och O. S känner till summan X+Y , P känner till produkten X·Y , och observatören O vet inget mer än den ursprungliga problemformuleringen. Alla tre parter behåller samma information men tolkar den olika. Då blir det ett informationsspel.

Låt oss kalla uppdelningen av ett tal A i två termer A=B+C för en 2-delning. Det behövs ingen avancerad kunskap som Goldbachs gissning eller det faktum att för att produkten B·C i en sådan 2-delning ska vara unik (dvs. det finns inga andra två tal som också när de multipliceras ger samma resultat). Men med Goldbachs gissning, tillsammans med det faktum att P omedelbart skulle känna till X och Y om deras produkt var ett halvprimtal , kan man dra slutsatsen att summan x+y inte kan vara jämn, eftersom varje jämnt tal kan skrivas som summan av två primtal. Produkten av dessa två tal skulle då vara ett halvprimtal.

Steg 1. S (Sue), P (Pete) och O (Otto) gör tabeller över alla produkter som kan bildas av 2-delar av summorna i intervallet, dvs från 5 till 100 ( X > 1 och Y > X kräver att vi börjar på 5). Till exempel kan 11 vara 2-delad i 2+9, 3+8, 4+7 och 5+6. De respektive produkterna är 18, 24, 28 och 30 och spelarna sätter en bock bredvid var och en av dessa produkter i sina tabeller (tabell 1). När de är klara har vissa nummer inga bockar, vissa har en och vissa har fler än en.

Steg 2. Sue tittar nu på sin summa och alla dess 2-delningar. Hon ser att alla 2-delar har produkter som inte är unika, dvs det finns en annan faktorisering som är en 2-delning av någon annan möjlig summa. Det ser hon från tabellen i steg 1 där alla hennes produkter har mer än en bock. Hon inser att på grund av detta faktum kommer Pete inte att kunna bestämma faktorerna X och Y på ett unikt sätt genom att titta på produkten (som skulle ha krävt att minst en av kandidatprodukterna bara hade en bock). Så hon utbrister "P kan inte veta X och Y ". När Pete och Otto hör detta får de informationen att ingen av produkterna som är kopplade till Sues summa är unika. Genom att gå igenom de möjliga summorna, en efter en, kan Sue, Pete och Otto nu, var och en för sig, göra en lista över alla berättigade summor (tabell 2). Tabellen innehåller de summor vars 2-delar har produkter som är icke-unika, dvs har mer än en bock i Tabell 1. Sue, Pete och Otto har skapat tabellen med kandidatsummor (Sue känner förstås henne redan summa men behöver spåra Petes tänkande).

Steg 3. Med tanke på den nya informationen i Tabell 2 tittar Pete återigen på sin produkt. Summorna av alla möjliga 2-delar av hans produkt utom en har försvunnit från tabell 2 jämfört med alla siffror mellan 5 och 100 som ansågs vara summor från början. Det enda som återstår måste vara summan av de två dolda talen X och Y vars produkt X·Y han känner till. Från summan och produkten är det lätt att veta de enskilda talen och därmed säger han till Sue att "Nu vet jag X och Y ". Pete är nu klar och lämnar spelet.

Steg 4. Sue och Otto räknar om tabell 1, denna gång räknar man bara produkter av 2-delar från summor som finns i tabell 2 istället för från alla tal i intervallet 5 till 100 som i den ursprungliga tabell 1. Denna uppdaterade tabell kallas tabell IB. Sue tittar på alla produkterna av 2-delarna av sin summa och finner att bara en av dem förekommer exakt en gång i Tabell 1B. Detta måste då vara produkten Pete har, och hon kan sluta sig till de två talen från deras summa och produkt lika lätt som Pete gjorde. Således säger hon till Otto (Pete är redan borta) att "Nu känner jag också X och Y ". Sue är nu också klar och går ur spelet, bara Otto är kvar.

Steg 5. Från informationen i steg 4, scannar Otto alla summor i Tabell 2 i sökning efter en av vilka endast en enskild 2-del har en enda bock i Tabell 1B. Den önskade kan bara ha en bock, annars skulle Sue inte ha kunnat veta X och Y med säkerhet. Slutligen kommer Otto fram till den önskade summan som också råkar vara den enda med dessa egenskaper, vilket gör det ursprungliga problemet lösbart med en unik lösning. Ottos uppgift är nu också klar.

Lösning

Lösningen har X och Y som 4 och 13, där P från början vet att produkten är 52 och S vet att summan är 17.

Till en början känner inte P till lösningen, eftersom

52 = 4 × 13 = 2 × 26

och S vet att P inte känner till lösningen eftersom alla möjliga summor till 17 inom begränsningarna ger liknande tvetydiga produkter. Men var och en kan komma fram till lösningen genom att eliminera andra möjligheter efter den andres uttalanden och det räcker för att läsaren ska hitta lösningen med tanke på begränsningarna.

Andra lösningar

Problemet kan generaliseras. Den bundna X + Y ≤ 100 är vald ganska medvetet. Om gränsen för X + Y ändras kan antalet lösningar ändras. För X + Y < 62 finns det ingen lösning. Detta kan till en början verka kontraintuitivt eftersom lösningen X = 4, Y = 13 passar inom gränsen. Men genom att utesluta produkter med faktorer som summerar till siffror mellan dessa gränser, finns det inte längre flera sätt att faktorisera alla icke-lösningar, vilket leder till att informationen inte ger någon lösning alls på problemet. Till exempel, om X = 2, Y = 62, X + Y = 64, X · Y =124 inte beaktas, så återstår bara en produkt av 124, dvs. 4·31, vilket ger summan 35. Sedan elimineras 35 när S deklarerar att P inte kan känna till produktens faktorer, vilket det inte skulle ha varit om summan av 64 var tillåten.

Å andra sidan, när gränsen är X + Y ≤ 1685 eller högre, visas en andra lösning X = 4, Y = 61. Från och med då är problemet alltså inte lösbart i den meningen att det inte längre finns en unik lösning. På liknande sätt, om X + Y ≤ 1970 eller högre uppträder en tredje lösning ( X = 16, Y = 73). Alla dessa tre lösningar innehåller ett primtal. Den första lösningen utan primtal är den fjärde som visas vid X + Y ≤ 2522 eller högre med värdena X = 16 = 2·2·2·2 och Y = 111 = 3·37.

Om villkoret Y > X > 1 ändras till Y > X > 2 finns det en unik lösning för tröskelvärden X + Y ≤ t för 124 < t < 5045, varefter det finns flera lösningar. Vid 124 och under finns inga lösningar. Det är inte förvånande att tröskeln för en lösning har gått upp. Intuitivt blev problemutrymmet "glesare" när primtal 2 inte längre är tillgängligt som faktorn X , vilket skapar färre möjliga produkter X·Y från en given summa A . När det finns många lösningar, det vill säga för högre t , sammanfaller vissa lösningar med de för det ursprungliga problemet med Y > X > 1, till exempel X = 16, Y = 163.

Om villkoret X + Y ≤ t för någon tröskel t byts ut mot X·Y ≤ u istället, ändrar problemet utseende. Det blir lättare att lösa med mindre beräkningar som krävs. Ett rimligt värde för u skulle kunna vara u = t · t /4 för motsvarande t baserat på den största produkten av två faktorer vars summa t är ( t /2)·( t /2). Nu har problemet en unik lösning i intervallen 47 < t < 60, 71 < t < 80, 107 < t < 128 och 131 < t < 144 och ingen lösning under det tröskelvärdet. Resultaten för den alternativa formuleringen överensstämmer inte med de för den ursprungliga formuleringen, varken i antal lösningar eller innehåll.

Se även

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Sum_and_Product_Puzzle&oldid=1138646668 "