Numere cu cifre distincte
On ianuarie 11, 2021 by adminLuați în considerare setul de numere naturale de la 0 la 999, inclusiv. Să presupunem că selectăm un subset al acestui set astfel încât orice pereche de numere din acesta să nu aibă mai mult de o cifră în aceleași poziții. Pentru a clarifica,
- Perechile precum 123 și 456 sunt permise în mod evident, deoarece nu au niciun fel de cifre în comun.
- 123 și 321 sunt permise împreună, deși au aceleași cifre exacte, doar 2 sunt de fapt în aceeași poziție.
- 812 și 212 nu ar fi permise, deoarece ambele împart „12” la sfârșitul lor, care este format din două cifre.
- 206 și 246 nu sunt permise în mod similar; cifrele partajate nu trebuie să fie contigue.
- Niciunul zero contează, deci 5 și 205 sunt o pereche interzisă ca bine. (Gândiți-vă la 5 ca la „005”.)
Amintiți-vă că acest lucru trebuie păstrat pentru fiecare pereche de numere din subset. Care este cel mai mare set (ca în majoritatea elementelor ) set posibil care îndeplinește această condiție? Ce zici de setul cu cea mai mare sumă de elemente?
(Puzzle inspirat de o conversație cu un prieten cu privire la introducerea greșită a numerelor de identificare. Îmi cer scuze dacă acest lucru a fost deja întrebat aici.)
Răspunde
Pentru ce merită, Am o vizualizare îngrijită a motivului pentru care răspunsul este 100:
În primul rând imaginați-vă un caz mai ușor, în care aveți toate numerele 0-99 și nu puteți avea niciun număr de două care să împartă orice cifră în același loc; putem desena un tabel de numere ca acesta:
Rețineți că fiecare număr dintr-un rând își împarte prima cifră, iar fiecare număr dintr-o coloană împarte a doua sa cifră. Prin urmare, trebuie să alegeți numere astfel încât niciunul să nu împartă un rând sau o coloană. Este destul de clar că cantitatea maximă de numere pe care o veți putea alege este 10. Aici este singura soluție:
Acum luați în considerare cazul pus în întrebare. Obțineți 10 din aceste tabele 0..99, cu excepția celui de-al doilea tabel conține 100..199, al treilea 200..299 și așa mai departe. Apoi puneți-le unul în spatele celuilalt pentru a forma un Grilă 10x10x10 de la 0..999 (am introdus câteva numere pentru a vă da ideea):
Rețineți că fiecare număr din orice „bandă” din zece cuburi (rând sau coloană) împărtășesc 2 cifre în comun. Prin urmare, trebuie să alegeți numere astfel încât niciun număr să nu împartă o „bandă”.
După ce ați gândit puțin, este clar că veți putea doar pentru a alege 100 de astfel de numere.
Răspuns
Pentru a adăuga la PrisonMonkeys „răspuns, fiecare set cu 100 de elemente vor avea aceeași sumă, adică 49950. Pentru fiecare loc din număr, fiecare cifră poate apărea numai în acel loc e cel mult de 10 ori, deoarece nu poate apărea cu aceeași valoare pentru un alt loc de două ori. Aceasta înseamnă că fiecare cifră trebuie să apară în fiecare loc exact de 10 ori, pentru a exista un total de 100 de numere în set. Prin urmare, putem însuma fiecare loc separat pentru a obține 45000 + 4500 + 450 = 49950.
Răspuns
Am o soluție cu 100 elemente din set. Generați fiecare număr după cum urmează:
Pentru elementul $ 0 \ leq n \ leq 99 $, adăugați
ABC
la setul în careAB
este $ n $ (cu un zero inițial dacă $ n < 10 $) șiC
esteA+B mod 10
. Deci, pentru $ n = 3 $,AB
este03
șiC
este0+3 mod 10=3
, adicăABC
este033
.
Nu există perechi de numere în acest set care încalcă condiția (din câte știu eu, adică). Și nu există un număr de trei cifre ABC
cu o altă parte AB
, deoarece am acoperit toate cele 100 de posibilități. Ceea ce înseamnă că acesta este cel mai mare set posibil care îndeplinește condiția.
Încă nu am nicio soluție pentru a doua întrebare.
AB
este57
(A=5
șiB=7
) șiC
este5+7 mod 10=2
, deciABC
este572
.