17. ESERCIZIO DIMOSTRATIVO
In quanti modi diversi si possono mettere in fila i numeri {21,31,41,51,61,71,81} in modo che, comunque se ne scelgano quattro in posti consecutivi, la loro somma sia divisibile per tre?
SOLUZIONE
Innanzitutto, trovo tutte le quaterne ideali, che definisco come quelle costituite da numeri la cui somma sia un multiplo di 3 e che permettono di ottenere altre quaterne ideali nella stessa sequenza.
Sapendo che la somma dei numeri in ogni quaterna dev’essere divisibile per 3 e che la somma di più numeri è divisibile per x t.c. x ∈ ℤ se e solo se lo è la somma dei resti nella divisione per x, si possono sostituire i numeri elencati con i loro resti nella divisione per 3. Notando che 21 ≡ 51 ≡ 81 ≡ 0 (mod 3), 31 ≡ 61 ≡ 1 (mod 3) e 41 ≡ 71 ≡ 2 (mod 3), si possono distinguere i sette numeri iniziali in 3 gruppi di numeri che danno lo stesso resto nella divisione per 3 (che può essere solamente 0, 1 o 2).
Si dispone, quindi, di {0,0,0,1,1,2,2} per formare quaterne di numeri consecutivi la cui somma sia divisibile per tre.
-Si possono individuare delle condizioni sufficienti per le quaterne ideali:
1) Non possono contenere tutti e tre i numeri di resto “0”, altrimenti, rimanendo solo quelli di tipo “1” e “2”, si avrebbero quaterne del tipo 0001 o 0002, che non sono ideali;
2) Non possono contenere un solo numero di tipo “0”, in quanto né le quaterne 0112 né quelle 0122 sono ideali;
3) Devono contenere almeno un numero di resto “0”, altrimenti non permetterebbero di ottenere altre quaterne ideali in nessun caso, pur essendo cosituite da numeri la cui somma divide esattamente 3. Infatti:
- Se posta in apertura o in chiusura, la quaterna (quella che completa la serie di 7 numeri) sarebbe costituita da 3 numeri di resto 0, e questo non è accettabile per la proprietà 1),
- Se occupasse i posti dal secondo al quinto o dal terzo al sesto, allora i tre numeri adiacenti ad essa dovrebbero avere resto 0, ma questo renderebbe una delle due quaterne, rispettivamente o iniziale o finale, formata da un solo numero di tipo “0”, e questo contraddirebbe la proprietà 2) (per esempio, in 0122100, dove la quaterna senza numeri di tipo “0” occupa i posti dal secondo al quinto, tutte le serie di quattro numeri consecutivi sono accettabili tranne quella che si forma necessariamente in apertura, 0122, che appunto non rispetta la seconda proprietà).
I numeri di tipo “0” sono 3
--> Ogni quaterna ideale deve contenere 2 numeri di resto “0” per esclusione
I posti totali sono sette
--> Le quaterne iniziale e finale condividono una posizione, che deve necessariamente occupare un numero di tipo “0”.
Sapendo che i numeri nelle quaterne cercate devono avere somma multipla di 3 e che ciascuna deve contenere due numeri divisibili per 3, rimanendo solo quelli di tipo “1” e “2”, l’unico tipo di coppia che può completarle adeguatamente è (1,2).
A questo punto, tutte le quaterne ideali sono quelle costituite da un numero di resto 1, uno di resto 2 e due di resto 0 in cui uno di questi ultimi due è fisso nel quarto posto dei sette, perché quella posizione è in comune a tutte le quaterne; in esse sono possibili tutte le permutazioni della terna rimanente. Per esempio, è ideale la quaterna 1200, purché nella posizione centrale delle sette si trovi fissato lo zero; dunque se tale quaterna è la prima della serie lo zero dovrà occupare la quarta posizione, mentre se si tratta dell'ultima allora si troverà fissato nella prima.
Adesso si consideri tutta la fila dei sette numeri, nella quale uno dei tre di tipo “0” si trova in posizione centrale, e si inserisca la prima quaterna ideale. A questo punto rimane un numero per tipo (0001122, dove quelli in rosso sono quelli utilizzati per la prima quaterna). Affinché ognuna delle tre sequenze di 4 numeri consecutivi oltre la prima risulti divisibile per 3, bisogna aggiungere un numero per tipologia alla volta e si può dimostrare che il quinto numero deve avere lo stesso resto del primo, il sesto quello del secondo e l’ultimo lo stesso del terzo:
Ip: Siano a, b, c i tre possibili resti che i numeri possono dare,
quindi a,b,c ∈ {0,1,2}, a ≠ b ≠ c.
Chiamando x, y, z i tre resti da aggiungere alla quaterna ideale iniziale, senza supporre che siano diversi tra loro, si ha allo stesso modo che x,y,z ∈ {0,1,2}.
Dim: a,b,c ∈ {0,1,2}, a ≠ b ≠ c per ipotesi
--> {a,b,c} = {0,1,2} (sempre a meno dell’ordine, che è proprio il motivo per cui ho deciso di indicare i resti con tre lettere, che possono assumere diversi valori in base al caso considerato)
x,y,z ∈ {0,1,2} per ipotesi
--> x,y,z ∈ {a,b,c}
Dato che uno tra a, b e c è uguale a 0 e gli altri due sono uguali a 1 e 2, la quaterna abc0, soddisfacendo tutte le condizioni sufficienti, rappresenta adeguatamente una ideale generica, dell’unica forma possibile.
Se la quaterna successiva dev’essere anch’essa ideale, considerando tutta la sequenza come abc0xyz (infatti si può definire l’ordine, purché non si definisca il valore delle singole lettere, sapendo che si trovano nell’intervallo {0,1,2}), significa che b+c+0+x ≡ 0 (mod 3)
x ≡ -(b+c) (mod 3)
x,y,z ∈ {a,b,c} per dimostrazione precedente
Si proceda per esclusione:
1) x=b
b ≡ -(b+c) per transitività
2b ≡ -c
c ≡ -2b (mod 3)
b,c ∈ {0,1,2}, b ≠ c per ipotesi
ASSURDO per ogni valore di b: c potrebbe essere rispettivamente congruo a 0, ma diventerebbe inammissibilmente uguale a b, oppure, se b=1, a -2 e, se b=2, a -4; tuttavia, al fine di rispettare queste condizioni restando al contempo nel suo intervallo c risulterebbe sempre uguale a b (in altre parole, il valore di c che soddisfa la relazione c ≡ -2b (mod 3), da scegliersi tra 0,1 e 2, è uguale a quello di b per ogni valore che b può assumere nell'intervallo {0,1,2}).
2) x=c
In modo analogo, si ottiene che b ≡ -2c e si dimostra che ciò è ASSURDO
--> x=a per esclusione.
Allora la sequenza sarà abc0ayz e, procedendo esattamente come prima, si ottiene che y e z possono essere solo uguali rispettivamente a b e c; così si ottiene che tutte le sequenze accettabili sono quelle del tipo abc0abc, dove a,b,c sono i tre resti che i numeri (elencati all’inizio) possono dare nella divisione per 3, ovvero (a,b,c) = (0,1,2) e vanno bene tutte le permutazioni di questa terna ordinata.
Pertanto, il modo di mettere in fila i numeri appartenenti alla terna finale è univocamente determinato. Allora il numero di modi complessivi di mettere in fila i sette numeri in modo da rispettare le proprietà indicate dipende solo da quello dei modi in cui mettere in fila i primi 3 e da tutti i modi possibili di sostituire al resto nella divisione per 3 con i numeri iniziali che lo danno.
-A questo punto è possibile calcolare quanto richiesto:
le permutazioni complessive della terna iniziale (ma si potrebbe procedere anche partendo da quella finale, dato che sono totalmente corrispondenti) sono 3!;
il secondo numero di tipo “0” è al centro, in quarta posizione, e l’ordine della terna dall’altra parte è univocamente determinato. Si ricordi, però, che vi sono tre numeri di resto 0, due di resto 1 e uguale quantità per quelli di resto 2, quindi bisogna ancora scegliere a quale dei resti sostituirli: per i multipli di 3, i modi di scegliere dove vanno sono 3!, dato che i posti equivalgono agli oggetti da inserire (3), e lo stesso vale per quelli di resto 1 e 2, che sono 2 per ciascun tipo, e quindi una volta scelto dove collocare il primo l’altro è obbligato (le possibili permutazioni per ognuno di questi due gruppi sono 2!=2).
Pertanto nₜₒₜ= n. permutazioni della terna (iniziale o finale) scelta x 2! x 2! x 3! (numero di modi di inserire i numeri iniziali, divisi in gruppi in base al resto dato nella divisione per 3, al posto del loro resto una volta fissata una permutazione) = 3! x (2!)² x 3! = (3!)² x (2!)² = (3! x 2!)² = (6x2)² = 12² = 144
Il numero di modi diversi in cui si possono mettere in fila i numeri {21,31,41,51,61,71,81} così che, comunque se ne scelgano quattro in posti consecutivi, la loro somma sia divisibile per tre, è 144. //