Newsgroup: it.hobby.enigmi
Titolo: Targhe

Nel paese di Vatteallapesca stanno introducendo le nuove targhe
automobilistiche, che saranno composte da 6 cifre. Per evitare possibili
confusioni e' stato proposto che vi siano almeno 2 cifre differenti fra
una targa e l'altra. 
Quante targhe potranno essere stampate rispettando questa restrizione ??
:)dario

Dario Uri ha scritto nel messaggio ...
ma non aveva altro da fare?

Dario Uri ha scritto:

Questi problemi dall'aria dimessa che sembrano risolvibili con un po' di
calcolo combinatorio...
Sono arrivato ad una congettura: il massimo numero di targhe che si possono
realizzare con il vincolo proposto e' 100.000
Consideriamo prima il problema con sole tre cifre. Immaginiamo un cubo
10X10X10 in cui ogni cubetto rappresenta una targa, e precisamente la targa
xyz dove x,y,z sono le coordinate del cubetto. Supponiamo di colorare in
rosso i cubetti relativi alle targhe valide.
Il vincolo delle due cifre differenti e' equivalente all'affermazione che
non ci devono essere cubetti rossi che differiscono per una sola
coordinata. Quindi in ogni fila, nel senso della lunghezza, della larghezza
o della profondita', ci deve essere al massimo un cubetto. Uno schema del
genere in tre dimensioni e' facilmente realizzabile riempiendo un quadrato
latino 10x10, con piu' cifre perdendo il supporto del disegno trovo qualche
difficolta', ma credo che la cosa resti vera, anche se non so nulla di
ipercubi latini.
Ciao, Silvio

 Ciao, Silvio
Bel ragionamento. In effetti sono proprio 10^5.
Prendendo in considerazione i primi 5 simboli, dovranno differire almeno
per una cifra.   Per ciascuna posizione
posso scegliere fra 0...9 ottenendo appunto 10^5 numeri con almeno una
cifra differente, questo e' il limite massimo. Ora bisognera' vedere se
effettivamente questo limite puo' essere raggiunto. Tutti i numeri che
hanno gia' 2 cifre differenti sono conformi alla regola. Per i restanti,
che nelle prime 5 cifre sono differenti solo in una posizione,
bisognera' che la sesta cifra sia diversa. Ecco una semplice procedura
che garantisce questo risultato. Sommo le 5 cifre presenti nel numero, e
considero come sesta cifra le unita' della somma ottenuta.
Es.
12345 somma 15 diventa 123455
12346   "   16    "    123466
12349   "   19    "    123499...
56789   "   35    "    567895 
56780   "   26    "    567806... 
ciao :)dario

 56780   "   26    "    567806... 
Davvero notevole, per semplicita' ed efficacia.
Se a Vattelapesca utilizzano proprio questo metodo, quante sono le targhe
con due sole cifre, ciascuna ripetuta tre volte?
piu' in generale, quante quelle che usano due cifre sole?
Ciao, Silv:o)

 
Quindi confermi quello che pensavo, cioe' che esiste un ipercubo latino di
qualsiasi dimensione ed ordine, e suggerisci anche un metodo costruttivo
per riempirlo: in ogni casella va messa la somma (modulo n) delle
coordinate.
Per chi non lo sapesse i quadrati latini di ordine n sono dei quadrati in
cui le caselle vanno riempite con n simboli in modo che in ogni riga e
colonna ci sia uno ed uno solo simbolo di ogni tipo:
esempio di ordine 4:
0 1 2 3
1 2 3 0
2 3 0 1
3 0 1 2
dove le quattro cifre compaiono una sola volta in ogni riga e colonna (l'ho
costruito secondo il metodo di Dario, cioe' ponendo nelle caselle la somma
delle coordinate modulo 4)
Esempio di cubo latino di ordine 3, riempito con lo stesso metodo:
  2----0----1 
 1----2----0:
0----1----2::
| 0..|.1..|:2
|2:  |0:  |1:
1----2----0::
| 1..|.2..|:0
|0   |1   |2
2----0----1
I quadrati latini sono molto usati nei giochi matematici, ed ancor di piu'
quelli greco-latini, ovvero quei quadrati formati sovrapponendo due
quadrati latini in modo che le coppie di simboli di ogni casella siano
distinte. Come curiosita' posso citare il fatto che sui quadrati
greco-latini prese una cantonata colossale nientemeno che Eulero, che
congetturo' l'impossibilita' di formare quadrati g.l. di ordine 10, ma
venne clamorosamente smentito (dopo quasi due secoli, pero').
Un esempio di problema e' il seguente:
Come si possono disporre 16 carte da poker (le figure piu' gli assi) in un
quadrato in modo che in ciascuna riga e colonna non ci siano mai due carte
uguali per seme o valore?
Varianti: i) Anche le diagonali devono godere della stessa proprieta'
         ii) I colori devono essere disposti a scacchiera
Ciao, Silv:o)