Siffror med distinkta siffror
On januari 11, 2021 by adminTänk på uppsättningen naturliga tal från 0 till 999 inklusive. Antag att vi väljer någon delmängd av denna uppsättning så att ett antal siffror från den delar högst en siffra i samma positioner. För att klargöra är
- Par som 123 och 456 uppenbarligen tillåtna eftersom de inte delar några siffror gemensamt.
- 123 och 321 är tillåtna tillsammans eftersom, medan de har samma exakta siffror, bara de 2 är faktiskt i samma position.
- 812 och 212 skulle inte tillåtas eftersom de båda delar ”12” i slutet, vilket är två siffror.
- 206 och 246 är inte tillåtna. De delade siffrorna behöver inte vara sammanhängande.
- Ledande nollor betyder, så 5 och 205 är ett förbjudet par som väl. (Tänk på 5 som ”005”.)
Kom ihåg att detta måste hållas för varje nummerpar i delmängden. Vilken är den största (som i de flesta element ) möjliga uppsättning som uppfyller detta villkor? Vad sägs om uppsättningen med den största summan av element?
(Pussel inspirerat av en konversation med en vän angående felskrivning av ID-nummer. Ber om ursäkt om detta redan har ställts här.)
Svar
För vad det är värt, Jag har en snygg visualisering av varför svaret är 100:
Föreställ dig först ett enklare fall där du har alla siffrorna 0-99 och du kan inte låta två nummer dela någon siffra på samma plats; vi kan rita en tabell med siffror så här:
Observera att varje nummer i en rad delar sin första siffra, och varje nummer i en kolumn delar sin andra siffra. Därför måste du välja siffror så att inga två delar en rad eller kolumn. Det är ganska tydligt att det maximala antalet siffror du kommer att kunna välja är 10. Här är en lösning:
Tänk nu på det fall som ställs i frågan. Få 10 av dessa 0..99 tabeller, förutom att den andra tabellen har 100..199, den tredje 200..299 och så vidare. Skikta sedan varandra efter varandra för att bilda en 10x10x10 rutnät från 0..999 (Jag har angett några av siffrorna för att ge dig idén):
Observera att varje nummer i valfri ”remsa” med tio kuber (rad eller kolumn) delar två siffror gemensamt. Därför måste du välja siffror så att inget nummer delar en ”remsa”.
Efter att ha funderat lite över är det tydligt att du bara kommer att kunna för att välja 100 sådana nummer.
Svar
För att lägga till i PrisonMonkeys ”svar, varje uppsättning med 100 element kommer att ha samma summa, vilket är 49950. För varje plats i numret kan varje siffra bara visas i den platsen e högst tio gånger, eftersom det inte kan visas med samma värde för en annan plats två gånger. Detta innebär att varje siffra måste visas på varje plats exakt 10 gånger, för att det ska finnas totalt 100 nummer i uppsättningen. Därför kan vi summera varje plats separat för att få 45000 + 4500 + 450 = 49950.
Svar
Jag har en lösning med 100 element i uppsättningen. Generera varje nummer enligt följande:
För element $ 0 \ leq n \ leq 99 $, lägg till
ABC
till uppsättningen därAB
är $ n $ (med en ledande noll om $ n < 10 $) ochC
ärA+B mod 10
. Så för $ n = 3 $ ärAB
03
ochC
är0+3 mod 10=3
, vilket betyderABC
är033
.
Det finns inga par siffror i denna uppsättning som bryter mot villkoret (såvitt jag vet är det). Och det finns inget tresiffrigt nummer ABC
med en annan AB
del, eftersom jag täckte alla 100 möjligheter. Vilket innebär att detta är den största möjliga uppsättningen som uppfyller villkoret.
Jag har ingen lösning på den andra frågan än.
AB
57
(A=5
ochB=7
), ochC
är5+7 mod 10=2
, såABC
är572
.