Numeri con cifre distinte
Su Gennaio 11, 2021 da adminConsidera linsieme di numeri naturali da 0 a 999, inclusi. Supponiamo di selezionare un sottoinsieme di questo insieme in modo tale che qualsiasi coppia di numeri da esso condivida non più di una cifra nelle stesse posizioni. Per chiarire,
- coppie come 123 e 456 sono ovviamente consentite poiché non condividono alcuna cifra in comune.
- 123 e 321 sono consentite insieme poiché, mentre hanno le stesse cifre esatte, solo il 2 è effettivamente nella stessa posizione.
- 812 e 212 non sarebbero consentiti poiché entrambi condividono il “12” alla fine, che è di due cifre.
- Allo stesso modo 206 e 246 non sono consentiti; le cifre condivise non devono essere contigue.
- Gli zeri iniziali sono importanti, quindi 5 e 205 sono una coppia proibita in quanto bene. (Pensa a 5 come “005”.)
Ricorda che questo deve valere per ogni coppia di numeri nel sottoinsieme. Qual è il più grande (come nella maggior parte degli elementi ) possibile insieme che soddisfa questa condizione? Che ne dici del set con la più grande sum di elementi?
(Puzzle ispirato da una conversazione con un amico per quanto riguarda lerrata digitazione dei numeri ID. Mi scuso se è già stato chiesto qui.)
Rispondi
Per quello che vale, Ho una chiara visualizzazione del motivo per cui la risposta è 100:
Prima immagina un caso più semplice, in cui hai tutti i numeri 0-99 e non puoi avere due numeri che condividono una cifra nello stesso posto; possiamo disegnare una tabella di numeri come questa:
Nota che ogni numero in una riga condivide la sua prima cifra e ogni numero in una colonna condivide la sua seconda cifra. Pertanto è necessario scegliere numeri in modo tale che nessuno condivida una riga o una colonna. È abbastanza chiaro che il numero massimo di numeri che potrai scegliere è 10. Ecco una soluzione:
Considera ora il caso posto nella domanda. Prendi 10 di queste 0..99 tabelle, eccetto che la seconda tabella ha 100..199, la terza 200..299 e così via. Quindi sovrapponile una dietro laltra per formare un Griglia 10x10x10 da 0..999 (ho inserito alcuni numeri per darti unidea):
Tieni presente che ogni numero in qualsiasi “striscia” di dieci cubi (riga o colonna) condivide 2 cifre in comune. Pertanto è necessario scegliere numeri in modo tale che nessun numero condivida una “striscia”.
Dopo aver riflettuto un po è chiaro che sarai in grado di per scegliere 100 di questi numeri.
Risposta
Per aggiungere alla risposta “PrisonMonkeys”, ogni serie con 100 elementi avranno la stessa somma, che è 49950. Per ogni posizione nel numero, ogni cifra può apparire solo in quella posizione e al massimo 10 volte, perché non può apparire due volte con lo stesso valore per un altro luogo. Ciò significa che ogni cifra deve apparire in ogni posizione esattamente 10 volte, affinché ci sia un totale di 100 numeri nel set. Pertanto possiamo sommare ogni posizione separatamente per ottenere 45000 + 4500 + 450 = 49950.
Risposta
Ho una soluzione con 100 elementi del set. Genera ogni numero come segue:
Per lelemento $ 0 \ leq n \ leq 99 $, aggiungi
ABC
a linsieme doveAB
è $ n $ (con uno zero iniziale se $ n < 10 $) eC
èA+B mod 10
. Pertanto per $ n = 3 $,AB
è03
eC
è0+3 mod 10=3
, che significaABC
è033
.
Non ci sono coppie di numeri in questo set che violano la condizione (per quanto ne so, cioè). Inoltre, non esiste un numero a tre cifre ABC
con una parte AB
diversa, poiché ho coperto tutte le 100 possibilità. Ciò significa che questo è linsieme più grande possibile che soddisfa la condizione.
Non ho ancora una soluzione per la seconda domanda.
AB
è57
(A=5
eB=7
) eC
è5+7 mod 10=2
, quindiABC
è572
.