Čísla s odlišnými číslicemi
On 11 ledna, 2021 by adminZvažte sadu přirozených čísel od 0 do 999 včetně. Předpokládejme, že vybereme nějakou podmnožinu této množiny tak, aby jakákoli dvojice čísel z ní nesdílela více než jednu číslici na stejných pozicích. Aby bylo jasno,
- páry jako 123 a 456 jsou samozřejmě povoleny, protože nesdílejí žádné společné číslice.
- 123 a 321 jsou povoleny společně, protože mají stejné přesné číslice, pouze 2 jsou ve skutečnosti na stejné pozici.
- 812 a 212 by nebyly povoleny, protože oba sdílejí „12“ na svém konci, což jsou dvě číslice.
- 206 a 246 nejsou obdobně povoleny; sdílené číslice nemusí být souvislé.
- Na počátečních nulech záleží, takže 5 a 205 jsou zakázané páry, protože studna. (5 si představte jako „005“.)
Nezapomeňte, že toto musí platit pro každou dvojici čísel v podmnožině. Co je největší (jako v většině prvků ) možné sadě, která splňuje tuto podmínku? Co třeba sada s největším součtem prvků?
(Puzzle inspirované rozhovorem s příteli ohledně překlepů ID čísel. Omlouvám se, pokud zde již bylo požádáno.)
Odpověď
Za to, co to má cenu, Mám úhlednou vizualizaci, proč je odpověď 100:
Nejprve si představte jednodušší případ, kdy máte všechna čísla 0-99 a nemůžete mít žádná dvě čísla sdílet libovolnou číslici na stejném místě; můžeme nakreslit tabulku čísel takto:
Všimněte si, že každé číslo v řádku sdílí svou první číslici a každé číslo ve sloupci sdílí svou druhou číslice. Proto musíte vybrat čísla tak, aby žádné dva nesdílely řádek nebo sloupec. Je jasné, že maximální počet čísel, která budete moci vybrat, je 10. Zde je jedno řešení:
Nyní zvažte případ uvedený v otázce. Získejte 10 z těchto 0..99 tabulek, kromě toho, že druhá tabulka má 100..199, třetí 200..299 atd. Poté je vrstvte jeden za druhým a vytvořte Mřížka 10x10x10 od 0..999 (pro představu jsem zadal některá z čísel):
Všimněte si, že každé číslo v libovolném „pruhu“ z deseti krychlí (řádek nebo sloupec) sdílí 2 číslice společně. Proto musíte vybrat čísla tak, aby žádné číslo nesdílelo „proužek“.
Po chvíli přemýšlení je jasné, že budete moci pouze vybrat 100 takových čísel.
Odpovědět
Chcete-li přidat do PrisonMonkeys „odpověď, každá sada s 100 prvků bude mít stejný součet, což je 49950. Pro každé místo v čísle se každá číslice může zobrazit pouze na tomto místě e nanejvýš 10krát, protože se pro jiné místo nemůže zobrazit dvakrát se stejnou hodnotou. To znamená, že každá číslice se musí na každém místě objevit přesně 10krát, aby v sadě bylo celkem 100 čísel. Proto můžeme každé místo sečíst samostatně, abychom získali 45 000 + 4500 + 450 = 49950.
Odpověď
Mám řešení se 100 prvky v sadě. Každé číslo vygenerujte takto:
U prvku $ 0 \ leq n \ leq 99 $ přidejte
ABC
do sada, kdeAB
je $ n $ (s úvodní nulou, pokud $ n < 10 $) aC
jeA+B mod 10
. Takže pro $ n = 3 $ jeAB
03
aC
0+3 mod 10=3
, což znamenáABC
je033
.
V této sadě nejsou žádné dvojice čísel, které by porušovaly podmínku (pokud vím). A neexistuje žádné trojciferné číslo ABC
s jinou AB
částí, protože jsem pokryl všech 100 možností. Což znamená, že se jedná o největší možnou množinu, která podmínku splňuje.
Pro druhou otázku zatím nemám řešení.
AB
je57
(A=5
aB=7
) aC
je5+7 mod 10=2
, takžeABC
je572
.