Liczby z różnymi cyframi
On 11 stycznia, 2021 by adminRozważmy zbiór liczb naturalnych od 0 do 999 włącznie. Załóżmy, że wybieramy jakiś podzbiór tego zbioru w taki sposób, że każda para liczb z niego ma nie więcej niż jedną cyfrę na tych samych pozycjach. Aby wyjaśnić,
- Pary takie jak 123 i 456 są oczywiście dozwolone, ponieważ nie mają wspólnych cyfr.
- 123 i 321 są dozwolone razem, ponieważ mają te same dokładne cyfry, tylko 2 znajduje się w rzeczywistości na tej samej pozycji.
- 812 i 212 byłyby niedozwolone , ponieważ obie mają wspólną „12” na końcu, to dwie cyfry.
- 206 i 246 są podobnie niedozwolone; wspólne cyfry nie muszą być ciągłe.
- Zera wiodące mają znaczenie, więc 5 i 205 są niedozwoloną parą, ponieważ dobrze. (Potraktuj 5 jako „005”).
Pamiętaj, że musi to dotyczyć każdej pary liczb w podzbiorze. Jaki jest największy (jak w większości elementów ) możliwy zbiór, który spełnia ten warunek? A co z zestawem z największą sumą elementów?
(Puzzle inspirowane rozmową z znajomego w związku z błędami w wpisywaniu numerów identyfikacyjnych. Przepraszamy, jeśli już o to pytano.)
Odpowiedź
Ale warto, Mam zgrabną wizualizację, dlaczego odpowiedź to 100:
Najpierw wyobraź sobie łatwiejszy przypadek, w którym masz wszystkie liczby od 0 do 99 i nie możesz mieć dwóch liczb, które mają wspólną dowolną cyfrę w tym samym miejscu; możemy narysować tabelę liczb w ten sposób:
Zwróć uwagę, że każda liczba w wierszu ma wspólną pierwszą cyfrę, a każda liczba w kolumnie ma drugą cyfra. Dlatego musisz wybierać liczby w taki sposób, aby żadne dwa nie miały wspólnego wiersza ani kolumny. Jest całkiem jasne, że maksymalna liczba liczb, które będziesz w stanie wybrać, to 10. Oto jedno rozwiązanie:
Rozważmy teraz przypadek przedstawiony w pytaniu. Pobierz 10 z tych tabel 0..99, z wyjątkiem drugiej tabeli, która ma 100..199, trzecia 200..299 itd. Następnie ułóż je jedna za drugą, aby utworzyć Siatka 10x10x10 od 0..999 (wpisałem kilka liczb, aby dać ci pomysł):
Zwróć uwagę, że każda liczba w dowolnym „pasku” dziesięciu kostek (wiersz lub kolumna) ma wspólne 2 cyfry. Dlatego musisz wybrać takie liczby, aby żadna liczba nie dzieliła „paska”.
Po chwili zastanowienia staje się jasne, że będziesz w stanie aby wybrać 100 takich numerów.
Odpowiedz
Aby dodać do PrisonMonkeys „odpowiedź, każdy zestaw z 100 elementów będzie miało tę samą sumę, czyli 49950. Dla każdego miejsca w numerze każda cyfra może pojawić się tylko w tym miejscu e najwyżej 10 razy, ponieważ nie może pojawić się dwukrotnie z tą samą wartością dla innego miejsca. Oznacza to, że każda cyfra musi pojawić się w każdym miejscu dokładnie 10 razy, aby w zestawie było łącznie 100 liczb. Dlatego możemy zsumować każde miejsce osobno, aby uzyskać 45000 + 4500 + 450 = 49950.
Odpowiedź
Mam rozwiązanie ze 100 elementy w zestawie. Wygeneruj każdą liczbę w następujący sposób:
Dla elementu $ 0 \ leq n \ leq 99 $ dodaj
ABC
do zbiór, w którymAB
to $ n $ (z zerem na początku, jeśli $ n < 10 $) iC
jestA+B mod 10
. Więc dla $ n = 3 $AB
to03
, aC
to0+3 mod 10=3
, co oznacza, żeABC
to033
.
W tym zbiorze nie ma par liczb, które naruszałyby warunek (o ile wiem, to znaczy). I nie ma trzycyfrowej liczby ABC
z inną częścią AB
, ponieważ omówiłem wszystkie 100 możliwości. Co oznacza, że jest to największy możliwy zestaw spełniający warunek.
Nie mam jeszcze rozwiązania drugiego pytania.
AB
to57
(A=5
iB=7
), aC
to5+7 mod 10=2
, więcABC
to572
.