Newsgroup: it.hobby.enigmi
Titolo: Anagramma divisibile

D'accordissimo con Le Regole Del Gioco.
Ho un certo numero di biglietti con scritte le cifre da 0 a 9. Esistono
almeno 2 biglietti con 2 cifre diverse. Mettendo in fila questi biglietti
posso formare diversi numeri (non considero le cifre 0 a sinistra).
Es: Ho i biglietti 1, 1, 0, 2
posso formare 112, 121, 211, 1012, 1021, 1102, 1120, 1201, 1210, 2011, 2101,
2110.
Di questi numeri formati prendo poi  il massimo comun divisore (x). Nel
nostro esempio e' 1 poiche' 121 e 112 sono primi fra loro.
-Quanto puo' valere x al massimo?
-Qual e' il minimo numero di bigliettini per ottenere tale x?
Mi scuso per la formulazione un po' bruttina...;-)
MF


Assolutamente ad occhio:
Col crescere delle cifre i numeri sono piu' grandi, ma anche il numero
di permutazioni.
Per ridurre il numero di permutazioni meglio adoperare poche cifre es:2
Un buon candidato potrebbe avere 4,5 cifre.
Meglio se le cifre non sono prime tra loro.
Da queste semplici premesse ed un paio di prove trovo:
6,6,6,9 = 27.
Una ricerca esaustiva richiede un po di tempo.

Una ricerca esaustiva richiede un po di tempo.
Acc... non riesco a capire il tuo ragionamento! Forse e' colpa della mia
formulazione del quesito. Ne do una in matematichese.
Sia X l'insieme dei numeri naturali che in base dieci NON si scrivono con
una sola cifra ripetuta piu' volte. Per ogni n di X definiamo A_n come
l'insieme dei numeri ottenuti permutando in tutti i modi possibili le cifre
di n e sia d_n il massimo comun  divisore di tutti i numeri di A_n. Ad
esempio, se n=1120,
A_1120=[112, 121, 211, 1012, 1021, 1102, 1120, 1201, 1210, 2011, 2101, 2110]
e d_1120=1 (112 e 121 primi fra loro).
Si determini il massimo valore possibile di d_n ed il minimo n avente tale
d_n associato.
Scusate, spero sia piu' chiaro.
MF

 Acc... non riesco a capire il tuo ragionamento! 
Non c'e' nessun ragionamento ragionato!
Penso d'aver capito il problema. Mi sembra pero' che un'analisi completa
richieda un procedimento complesso.
A sensazione, come ti ho detto, ho provato  con le permutazioni di
6,6,6,9:
I quattro numeri ottenibili: 9666, 6966, 6696, 6669  anno MCD=27.
Non so come puoi essere sicuro di avere la soluzione. Ad esempio,
potrebbe esistere un numero diciamo di 20 cifre, 19 tutte uguali + una
differente (questo minimizza il numero delle permutazioni) con un MCD
molto alto.
Non so, ci devo ancora pensare.

 Non so, ci devo ancora pensare.
Per il momento ammettiamo che l'ipotesi che ho fatto (2 sole cifre in
gioco) sia effettivamente la piu' conveniente, ma non lo posso provare.
Analizziamo allora una serie di cifre nel numero di n, dove n-1 sono
tutte uguali.
Procedo con un esempio:
Prendiamo 777...7772. Generando tutte le possibili permutazioni, e
mettendole in ordine di grandezza, posso osservare che se la differenza
dei primi 2 numeri e' X, la seconda sara' 10X, la terza 100X ecc, come
dire che tutti i termini successivi al primo saranno divisibili per X,
se anche il primo termine lo e'.
Supponiamo ci siano solo 4 cifre, allora:
7772
7727
7277
2777
Ora le differenze sono: 7772-7727=45, 7727-7277=450, 7277-2777=4500
In altre parole se il primo termine 7772, fosse divisibile per 45, tutti
gli altri lo sarebbero, ma allora posso controllare se esistono multipli
di 45 della forma 77...772. E' evidente che ogni multiplo di 45 termina
con la cifra 5, un caso impossibile.
A questo punto se voglio massimizzare il MCD mi conviene iniziare con le
cifre di differenza massima 9 e 2, (9,0 e 9,1 si manifestano subito come
casi impossibili) 
92-29 = 63 che e' il massimo ottenibile. Si tratta di vedere se esiste
un multiplo di 63 della forma 999...9992 oppure della forma 222...2229. 
Non occorre scrivere un programma, basta procedere a ritroso. Chiamiamo
y il numero da trovare deve essere 63*y=99...992.
la cifra a destra di y per dare il 2 deve essere 4, 4*63=252, sotto il 5
ci vuole 4 per sommare 9, la seconda cifra e'8 ecc.
ottengo Y=...126984
	63*...126984=
______________________
        	252
               504
              567
             378
            126
            63 
----------------------
         ...7999992 
Arrivati qui possiamo desistere infatti come si vede si entra in un
loop, ed il numero cercato non puo' essere ottenuto.
Procedendo in questo modo, ho testato :
9,2  8,1                     MCD = 63
9,3  8,2  7,1                 "  = 54
9,4  8,3  7,2  6,1            "  = 45
9,5  8,4  7,3  6,2            "  = 36
9,6  8,5  7,4  6,3            "  = 27
Per tutti o si entra in un loop, oppure e' impossibile per un fattore di
parita' (36*y non puo' dare un numero che termina con 5 o 9..)
La prima soluzione e' proprio quella trovata a naso 9,6.
6669, 6696, 6966, 9666 sono tutti divisibili per 27.
Abbiamo esplorato solo una piccola parte del problema, quella che mi e'
sembrata con maggiori possibilita'.
Con piu' cifre differenti, es: 1,2,3,4,5 hai 5!=120 numeri e la
probabilita' che ce ne siano 2 primi fra loro e molto alta. 
Non avendo trovato un attacco diretto al problema, aspettero' la tua
soluzione.
ciao  dario

ciao  dario
Il quesito era stato posto l'anno scorso alle finali italiane delle
Olimpiadi della M. ed e' uno dei pochi che ho risolto bene :] . La soluzione
ufficiale e' la seguente.
Il MCD di due numeri divide anche la loro differenza. Se A e B sono due
cifre distinte di n, con A>B, i due numeri ...XXXAB e ...XXXBA sono in A_n
(...XXX rappresenta una successione qls di cifre di n). La loro differenza
vale 9(A-B).
Il valore massimo di A-B e' 9, che si raggiunge solo se A=9 e B=0. Questo
dimostra che d_n e' minore o uguale a 81. Vediamo ora che esiste un intero N
tale che d_N=81. Un tale N deve essere formato solo da cifre 0 e 9
(altrimenti si trovano A e B come sopra, con A-B<9, mentre d_n<=9(A-B)<81) e
deve essere multiplo di 81.
[Fin qui il ragionamento e' simile al tuo, anche se non se perche' hai
escluso il caso con 9 e 0.]
Equivalentemente N/9 deve essere formato solo da cifre 1 e 0 e deve essere
multiplo di 9. Il piu' piccolo intero con queste proprieta' e' 1011111111,
quindi N e' almeno 
9099999999
. D'altra parte si verifica facilmente che
tutti i numeri di A_N sono divisibili per 81 e quindi d_N=81.
A presto J:-)
MF

 Per tutti o si entra in un loop, 
A mano devo aver pasticciato nel calcolo a ritroso della combinazione
8,2, dato che  e' stato estremamente lungo ho fatto una verifica. Ho
trovato che tutti i numeri formati da venti cifre "8" ed una cifra "2"
(notazione: 8(venti)+2(uno)) sono tutti divisibili per 54.
Il prossimo e' 2(ventitre)+8(uno).

 escluso il caso con 9 e 0.]
Me lo chiedo anch'io!

Il prossimo e' 2(ventitre)+8(uno).
Ho notato, esaminando la tua soluzione, che un numero formato da 8 e 2 che
sia divisibile per 54 resta tale permutando le cifre.
Percio' mi e' venuto il dubbio che sia possibile un altra soluzione...
Per esempio, usando la tua notazione, 8(sei)+2(tre).
Non sono sicuro che sia la soluzione migliore...
In ogni caso vorrei fare il punto della situazione.
1. Nella soluzione possiamo escludere la cifra 0, perche' altrimenti avremmo
un insieme piu' piccolo, togliendo lo 0, che soddisfa il problema.
2. Ho trovato molto utile l'algoritmo euclideo che dice:
MCD(a,b)=MCD(b,r)
dove intendo con MCD il massimo comun denominatore, a e b numeri qualsiasi,
r e' il resto della divisione tra a e b.
Con questo si puo' dimostrare che il MCD cercato non puo' essere superiore a
72.
Tutto questo, Dario, lo hai considerato implicito nelle tue soluzioni, io mi
limito a metterlo in evidenza.
Ora credo che avendo dimostrato che esistono insiemi con MCD=54, resta da
dimostrare che non ce ne sono con MCD=63 (anche se considero convincenti le
tue considerazioni), e che l'insieme trovato e' minimo (non ho molti dubbi a
riguardo, ma non sono sicuro).
Un ultima cosa riguardo la divisibilita' per 54:
se considero il numero decimale ...fedcba dove le lettere sono cifre, posso
dire che se
a*10+b(-8)+c*28+d*10+e*(-8)+f*28... (moltiplicando di seguito per 10, -8 e
28)
e' divisibile per 54, anche il numero originario lo e'.
Da questo ho potuto essere sicuro che, se le cifre sono 2 e 8, qualsiasi
permutazione rimane divisibile per 54.
Non vorrei fare la figura dell'avvoltoio... Dario ha fatto tutto il
lavoro...
Ma Matteo non ha ancora risposto, forse non ci siamo ancora???
Ciao ciao
Claudio

Il valore massimo di A-B e' 9, che si raggiunge solo se A=9 e B=0.
...
Diavolo!!!
Ho visto solo adesso il tuo messaggio... ci sono rimasto malissimo ;-)!
E' vero... lo zero si esclude solo se le altre cifre non sono tutte
uguali!!!!
Bellissimo il giochino e complimenti davvero per averlo risolto in
situazione difficile come durante una competizione!
Ciao ciao
Claudio superPOLLO! ;-)