termékeink legutóbbi rejtvénycsomag szerepelt a szerény, két serpenyős mérlegskálával, amely történelmileg a kereskedelem és a kormányzat, a művészet és a tudomány szimbóluma volt. A mérleg mérlegek a rekreációs matematikában is népszerűek. A mérlegrejtvények világos, logikus érvelést igényelnek, és jól alkalmazhatók a matematikai általánosításra. Lássuk hogyan Quanta Az olvasók ezeket a tulajdonságokat egyensúlyozták ki az alábbi rejtvényekben.
Rejtvény 1
Nyolc egyforma kinézetű érméd van. Az egyik hamisított és könnyebb, mint a többi, amelyek súlya azonos. Keresse meg a rossz érmét két mérlegelésben. Keresse meg az érmék maximális számának általános képletét, amelyben megtalálhatja a hamisított érmét x mérlegek.
Egy probléma egyszerű változatának kezelése gyakran felfedi a megoldás kulcsát. Ebben az esetben képzelje el, hogy csak három érméje van, amelyek közül az egyik világosabb, mint a másik kettő. Ha bármelyiket mérlegeli a másik kettő közül, akkor vagy egyensúlyban lesz, vagy nem. Ha nem, akkor tudja, melyik a könnyebb. Ha egyensúlyban vannak, akkor a harmadik a világos. Csak egyszeri mérlegelésre van szüksége.
Tehát ebben a feladványban, ha el tud különíteni egy három (vagy kevesebb) csoportot, amelyek az első mérlegeléskor a könnyű érmét tartalmazzák, akkor csak még egy mérlegelésre lesz szüksége. Ezt úgy teheti meg, hogy bármelyik hármat kiegyensúlyozza bármely másik hárommal. Ha a két csoport kiegyensúlyozatlan, akkor megtalálta a világos csoportot, és a második mérésnél a fentiek szerint járhat el. Ha egyensúlyban vannak, csak mérd egymáshoz a maradék két érmét, és megtalálod a világosat.
Figyeljük meg, hogy ez akkor is működik, ha hárman vannak a mérleg nélküli csoportban, tehát kilenc érmével is kezdhettünk volna. Ezt a logikát követve, három érmétől kezdve, minden további mérlegelésnél háromszor annyi érmében találhatjuk meg a világos érmét, mint amennyi korábban rendelkeztünk. A képlet, amely megadja a maximális érmék számát n in w mérlegek tehát n = 3w.
Rejtvény 2
12 egyforma kinézetű érméd van. Az egyik nehezebb vagy könnyebb, mint a többi, amelyek súlya azonos.
-
Keresse meg a rossz érmét három mérlegelésben.
-
Legfeljebb hány érméhez lehet négy mérlegeléskor megtalálni a rosszat? Írja le, hogyan találja meg a hamis érmét.
Ennek a rejtvénynek a megoldását jól leírta Ted, aki azt is megmutatta, hogy három mérlegelés során 13 érme között valóban megtalálhatja a rossz érmét. Íme Ted megoldása (behúzásokkal, amelyek minden esetben elválasztják a három mérést):
Kezdje a 4 érme és a 4 érme mérlegelésével.
1. eset: Ha kiegyensúlyozatlan, a második méréshez tegyen 2-1-t a nehezebb oldalak közül a mérleg mindkét oldalára, valamint XNUMX-XNUMX-et a könnyebb oldalra.
1a: Ha kiegyensúlyozatlan, a rossz érme vagy a 2 érme a nehéz oldalon, vagy az egyetlen érme, amely még mindig a könnyű oldalon van.
Mérjük meg a 2 lehetséges nehéz érmét, a rossz vagy a nehezebb a kettő közül, vagy az egyetlen könnyű, ha egyensúlyban vannak.
1b: Ha a második mérlegelés kiegyensúlyozott, akkor a rossz érme az első mérés könnyebbik oldaláról a 2 fel nem használt érme egyike.
Mérjük egymáshoz őket, a könnyebbik rossz.
2. eset: Ha kiegyensúlyozott, a rossz érme az 5 megmaradt érme egyike. Mérj ezek közül 3-at a már megmért 3-hoz (amelyről ismert, hogy jó).
2a. eset: Ha kiegyensúlyozatlan, akkor tudja, hogy a rossz érme a 3 egyike, és hogy könnyű vagy nehéz.
A harmadik mérlegelés bármelyik 2 egymáshoz mért értéke – ha kiegyensúlyozatlan, az a rossz érmét azonosítja, ha kiegyensúlyozott, akkor az utolsó a három közül.
2b eset: Ha a második mérlegelés kiegyensúlyozott, a rossz érme a maradék 2 érme egyike.
Mérje meg bármelyiket egy ismert jó érméhez képest. Ha ez az eredmény kiegyensúlyozatlan, akkor ez az új érme rossz, és tudod, hogy nehéz vagy könnyű. Ha ez az eredmény kiegyensúlyozott, akkor a 13. érme rossz, de nem tudni, hogy nehéz vagy könnyű (amit nem kell tudnunk, így készen vagyunk).
Ted azt is bemutatta, hogy a négy mérlegelésnél legfeljebb 40 érme lehet. A kirakós képlet a következő: n = (3w − 1)/2.
A fennmaradó rejtvények esetében az általánosított képleteket a professzionális matematikusok még vizsgálják, és publikációk tárgyát képezik, amelyek közül néhányat idézett Rainer aus dem Spring. A rejtvényekben figyelembe vett kis számú érme megoldására szorítkozom, és csak azokat az általánosításokat említem meg, amelyek természetesen következnek az ilyen esetekben alkalmazott módszerekből.
Rejtvény 3
Ez az 1. rejtvény egy változata. Ismét van nyolc egyforma kinézetű érméd, amelyek közül az egyik könnyebb, mint a többi. Most azonban három mérleged van. A mérlegek közül kettő működik, de a harmadik elromlott, és véletlenszerű eredményeket ad (ez néha helyes, néha rossz). Nem tudod, melyik mérleg törött. Hány mérlegelés szükséges ahhoz, hogy megtaláljuk a világos érmét?
Amint az 1. feladatban láttuk, ehhez mindössze két mérlegelés szükséges jó mérleg mellett. Azt is tudjuk, hogy a két jó mérleg mindig megegyezik, így ha csak megismételjük mindegyik mérlegelést mindhárom mérlegen, akkor hat mérlegelésben megkapjuk a választ, ahogy azt az olvasó javasolta. Ha kisebb számú méréssel próbáljuk megcsinálni, akkor kicsit trükkös lesz. Nem tudunk jó mérleget azonosítani pusztán úgy, hogy ugyanazokat az érméket két mérlegen lemérjük, mert még ha megegyeznek is, a kettő közül bármelyik lehet rossz mérleg. (Ez azt is mutatja, hogy a félretájékoztatás vagy a véletlenszerű információk mennyire könnyen elhomályosíthatják az igazságot.)
Valójában ez a probléma nagyon okosan, mindössze négy mérleggel megoldható! Rainer aus dem Spring közzétette a megoldást egy újszerű jelöléssel, amelyet úgy tűnik, hogy ehhez a rejtvényhez hozták létre. De mielőtt odamenne, azt akarom, hogy képzeljen el egy forgatókönyvet, amely reményeim szerint intuitívabbá teszi a dolgokat.
Képzelje el, hogy Ön egy nyomozó, aki egy kis országban ütközés után nyomoz, ahol az autók kétszámjegyű rendszáma csak a 0, 1 és 2 számjegyeket tartalmazza. Három ember, A, B és C, figyelte az esetet. Közülük ketten mindig helyesen válaszolnak egy háromválasztós kérdésre, egy pedig teljesen véletlenszerű választ ad. Nem tudod, ki a véletlen válaszoló. Mindegyiküknek fel kell tennie egy-egy három választásos kérdést, majd kiválaszthatja azt, aki határozottan igazat mond, hogy további információkat kapjon.
Íme, hogyan kell csinálni. Kérdezd meg A-t, hogy az első számjegy 0, 1 vagy 2. Tegyük fel, hogy A 2. Kérdezd meg B-t, ha a második számjegy 0, 1 vagy 2. Tegyük fel, hogy B azt mondja, hogy 1. Ezután kérd meg C-t, hogy válasszon a három állítás közül:
- Csak A mond igazat.
- Csak B mond igazat.
- Mindketten igazat mondanak.
Elhiheted azt, amit C mond, és megkérdezheted az illetőt a másik számjegyről. Hogy megértsük, miért, vegyük figyelembe, hogy ha A hazudik, akkor C megbízható, és azt mondja, hogy B igazat mond. A második számjegy valójában 1 lesz, és ezután megkérdőjelezheti a B-t az első számjegyről. Hasonlóképpen, ha B hazudik, akkor C ismét megbízható, és azt mondja, hogy A igazat mond. Ekkor az első számjegy valójában 2, és megkérdőjelezheti A-t a második számjegyről. Végül, ha C hazudik, akkor A és B is megbízható, így továbbra is hinni lehet és kiválasztani azt, akit C mond. (És ha C azt állítja, hogy A és B is igazat mond, akkor mindkettőnek igazat kell mondania.) A kulcs itt az, hogy a kérdések megválasztása ne engedje meg, hogy C úgy hazudjon, hogy kétségbe vonja A-t és B-t is. Mivel A és B közül legalább az egyiknek megbízhatónak kell lennie, mindig kiválaszthatja azt, amellyel C egyetért, még akkor is, ha az csak véletlenszerű válasz. Ha mindhárman egyetértenek, akkor már megvan a rendszám mindkét számjegye.
Így fordíthatjuk vissza ezt a mesét a rejtvényünkre. A skálák A, B és C. A rendszám két számjegyét a következőképpen fordíthatja le az érmékre: 01 az 1. érme, 02 a 2. érme, 10 a 3. érme, 11 a 4. érme, 12 az 5. érme, A 20 a 6-os érme, a 21 a 7-es, a 22 pedig a 8-as érme. Okos olvasók felismerik, hogy ez az alap 3-as (vagy hármas) számrendszer. Azt is vegye figyelembe, hogy van egy további lehetséges 00-as szám, amelyet felhasználhat egy kilencedik érméhez, amelynél ez a technika is működik, mint az 1. rejtvényben.
Az első mérésnél elosztod az érméket az első (3-as bázis) számjegyükkel, így a három csoportod az [1, 2], [3, 4, 5] és [6, 7, 8] érmék lesz. Mérje meg a [3, 4, 5] és [6, 7, 8] értékét az A mérlegen. Ha A jól működik, akkor a megfelelő első számjegycsoportot kapja, mint az 1. rejtvényben. Hasonlóképpen, a B skálán a második mérlegeléskor a csoportjai azonos második számjegyűek lesznek: [1, 4, 7], [2, 5, 8] és [3, 6]. Ha B jól működik, akkor a megfelelő második számjegy lesz. A harmadik mérlegelésnél a C skálán mérlegelje az A által azonosított csoportot a B által azonosított csoporthoz. Példánkat követve 21 esetén a csoportok a következők lesznek: [6, 7, 8] és [1, 4, 7]. A 7-es érmét nem lehet egyszerre mindkét oldalára feltenni, ezért kihagyjuk, és egymáshoz mérjük a [6, 8] és [1, 4] értékeket. Vegye figyelembe, hogy ha A és B is megbízható, akkor valójában a 7 a helyes válasz, és nem mindegy, hogy melyik oldal jön ki könnyebben C-n. Ha véletlenül a C-n a mérlegelés kiegyensúlyozott, akkor mindhárom mérleg megegyezik, és a válaszod (7-es érme) mindössze három mérlegeléssel rendelkezik. Ha A megbízható és B nem, akkor a világosabb érme a [6, 8]-ban van, amely C skála megerősíti, és ha B megbízható és A nem, akkor a világosabb érme az [1, 4]-ben van, amely C skála is megerősíti.
Tehát három mérlegelés során vagy azonosítottuk a világos érmét, vagy leszűkítettük egy kettős csoportra, és azonosítottunk egy működő mérleget is. Az A vagy B mérlegen végzett negyedik mérlegelés (amelyik a C mérleg megegyezik) elvégzi a többit.
Ez a megoldás elképesztően szépnek tűnik!
Ezt a módszert általánosíthatjuk úgy, hogy megtaláljuk a világos érmét a 3 között2x érmék a 3-banx + 1 mérlegelés a megadott mérlegkészlettel. Így 81 érméhez hét mérlegre van szükség. Nagyobb számú érme esetén (>~1,000) még erősebb megoldás létezik.
Rejtvény 4
16 érméd van, ebből nyolc nehéz és azonos súlyú. A többi nyolc könnyű és azonos súlyú. Nem tudod, melyik érmék nehéz vagy könnyűek. Az érmék egyformának tűnnek, kivéve egy különleges jelölést. Egy jó mérleggel három mérleggel meg tudod állapítani, hogy a különleges érme könnyű vagy nehéz? Legfeljebb hány érmével kezdheti el és sikeresen megoldhatja ezt a problémát négy mérlegelés során?
Első pillantásra úgy tűnik, hogy ezt a feladványt három mérlegelés alatt szinte lehetetlen megcsinálni, ahogy egy olvasónk összegezte. Ennek ellenére némi okossággal meg lehet csinálni, és mindkettő Ted és a Rainer aus dem Spring helyes megoldásokat adott. Ted felbecsülhetetlen értékű általános alapelvekkel szolgált, amelyekre érdemes odafigyelni.
Először is, amíg nem kap kiegyensúlyozatlan eredményt a mérlegelésből, nem lesz elegendő információja annak meghatározásához, hogy a speciális érme nehéz vagy könnyű. Tehát meg kell próbálnia kiegyensúlyozatlan eredményt elérni.
Másodszor, ha kiegyensúlyozott eredményt kap (mondjuk az A speciális érme kiegyensúlyozza a B érmét), összevonhatja a kiegyensúlyozott érméket, és összemérheti őket további két érmével, C-vel és D-vel. Ha kiegyensúlyozatlanok, akkor megvan a válasz; egyébként most megduplázta a hasonló érmék számát, ami segíthet kiegyensúlyozatlan választ kapni a következő mérlegeléskor. Ezt a folyamatot fordítva is végrehajthatja olyan számú érmével, amely kettő hatványa (4, 8 stb.), ha a következő megoldásban látható kezdeti kiegyensúlyozatlan eredményt kap.
Az alábbiakban látható a teljes eljárás, amellyel minden esetben három mérlegelés során azonosítható az A speciális érme típusa. (B, C és D három érme, amelyek az 1-es mérlegben A-val azonos oldalra vannak helyezve (W1); X és Y a W1-ben nem használt két érme.)
Ezt a rejtvényt egy orosz matematikus találta ki Konstantin Knop, az érmemérési rejtvények világtekintélye. Sok dolgozata orosz nyelvű, de számos érmerejtvényt (egyéb érdekes rejtvények mellett) is találhat az oldalon. blog munkatársa, Tanya Khovanova.
Ami az általánosítást illeti, rád bízom, hogy lásd, ugyanez a módszer működik-e egy speciális érme típusának megtalálására 32 érme közül, amelyek közül 16 nehéz és 16 könnyű.
Rejtvény 5
Van n egyforma kinézetű érmék, amelyek közül néhány hamis és könnyebb, mint a többi. Csak annyit tudsz, hogy van legalább egy hamis érme, és több a normál érme, mint a hamis. Az Ön feladata az összes hamis érme felderítése.
Az a tény, hogy van legalább egy világos érme, és több a normál érme, mint a könnyű érme, kevésbé bonyolulttá teszi ezt a rejtvényt, mint elsőre tűnik, legalábbis kis számok esetében. Nézzük meg az egy-nyolc érmére vonatkozó mérlegelési számokat.
Egy és két érméhez a második feltételhez nem lehet könnyű érme, így nincs szükség mérlegelésre.
Három érme: Csak egy könnyű érme. Rejtvényenként egy mérlegelés szükséges 1.
Négy érme: Csak egy könnyű érme. Egy további mérlegelés szükséges, tehát w = 2.
Öt érme: egy-két könnyű érme. Ez az első érdekes eset. A kérdés a következő: mérlegeljünk egy érmét egyhez, vagy két érmét kettőhöz?
Ha egyet az egyhez mérünk, akkor a következőket kaphatjuk:
- Két kiegyensúlyozatlan mérleg: Két érmét találtak; végeztünk.
- Egy kiegyensúlyozott mérleg a kettőből: A kiegyensúlyozott érméknek normálnak kell lenniük, így az utolsó érmét még egyszer meg kell mérni, w = 3.
- Két kiegyensúlyozott mérlegelés: A harmadik mérlegelésnél minden korábbi mérlegelésből egy érmét mérjen a másikhoz. Ha kiegyensúlyozottak, mind a négy normális, és az 5-ös érme a világos. Végeztünk; w = ismét 3. Ha kiegyensúlyozatlanok, megtaláltuk a két könnyű érmét, és három méréssel végeztünk.
Ha ehelyett kettőt kettőhöz mérünk, akkor is három mérlegelésre van szükségünk, mert különbséget kell tenni a között, hogy az érmék mindkét oldalon eltérőek vagy hasonlóak lehetnek. Úgy tűnik, hogy a kis számú érmék csoportosításával történő mérlegelésnek nincs előnye az egyetlen érmével történő méréssel szemben.
Ez a következőkre vonatkozik:
Hat érme: egy-két könnyű érme; w = 4.
Hét érme: egy-három könnyű érme; w = 5.
Nyolc érme: 1-3 könnyű érme; w = 6. Ennek a megoldásnak egyszerű a felépítése:
- Először négyszer mérlegelje az egyik érmét a másikkal szemben. Minden érmét használnak.
- A legrosszabb eset: Mind a négy mérleg kiegyensúlyozott (két könnyű érme van, amelyek kiegyensúlyozzák egymást).
- Következő két mérlegelés: Mérjünk le egy 1-es súlyú érmét a 2-es súlyú érmével szemben; hasonlóképpen mérjünk össze egy 3-as súlyú érmét egy 4-es súlyú érmével.
- Az egyik ilyen mérleg kiegyensúlyozatlan lesz, és azonosítja a két könnyű érmét. Hat mérleggel végeztünk.
Sajnáljuk, a 0, 0, 1, 2, 3, 4, 5, 6 sorozatunk biztosan nem elég érdekes ahhoz, hogy alávetjük magunkat a On-Line Encyclopedia of Integer Sequences!
As Jonas Tøgersen Kjellstadli rámutatott, a megoldás az w = n − 2 kis számoknál, de nem bizonyítottuk, hogy ez nagyobb számoknál nem fog változni. Néhánynál n, több érmeméréssel jobban teljesíthet, vagy több mérést végezhet, mint n − 2 szükséges lehet. Egyszerűen általánosíthatjuk a nyolc érmére vonatkozó megoldást a 2 minden hatványára, megadva n − 2 a mérések számának felső korlátja a 2 minden hatványa esetén.
Mark Pearson megvitatta ennek a problémának a hibajavító kódokhoz való hasonlóságát, és a lehetséges kimenetelek számán alapuló információelméleti megközelítés alkalmazását javasolta. Ilyen megközelítést alkalmazva, Mike Roberts alsó korlátot írt ki az általánosabb esetre, amely Rainer aus dem Spring közelítését származtatta. Rainer is közzétett egy felső határ egy publikált lapból, de megjegyezte, hogy a határok nem élesek az alacsony szintre n és ezért nem hasznos a fent említett kis számok esetében. Így hét érmére az idézett korlátok 4 és 16 közötti tartományt adnak, amelybe a mi válaszunk, az 5, közé esik. J. Payette további matematikai hivatkozásokat és korlátokat ad az összes rejtvényhez.
Köszönöm mindenkinek, aki részt vett. Az Insights díjat ebben a hónapban Ted és Rainer aus dem Spring közösen kapja. Gratulálunk!
Találkozunk legközelebb az újdonságért Insights.
