Introduzione
Matematicamente si tratta di risolvere l'equazione lineare: \begin{aligned} x_1+x_2+...+ x_k&=k\cdot M=n \end{aligned} \tag{1}
Senza perdita di generalità possiamo pensare alle sole soluzioni intere non negative dell'equazione. I voti, infatti, sono espressi, con numeri naturali o al più con numeri decimali con parte decimale in centesimi o millesimi e quindi l'equazione (1) è o, nel caso si ricorra a numeri decimali, può essere ricondotta (moltiplicando ambo i membri per 100 o per 1000) a un'equazione a variabili naturali.
Prima digressione matematica
L'equazione lineare a variabili naturali (1) è un'equazione lineare diofantea: le variabili x_1, x_2, ..., x_k e il termine noto n sono numeri naturali. Una soluzione dell’equazione è una k−upla di numeri naturali (p_1, p_2, ..., p_k) ∈ N^k che sostituiti ordinatamente alle variabili x_1, x_2, ..., x_k rendono l’equazione identicamente vera, ossia:
p_1 + p_2 + ... + p_k=n
e ciascuna componente p_i della quaterna soddisfa la condizione p_i ∈ \{0, 1, 2, 3, ..., n\}.
Il numero delle k-uple di interi non negativi che sono soluzioni dell’equazione diofantea (1) è dato da: \begin{align}\binom{n+k-1}{k-1}&=\binom{n+k-1}{n}\\&=\frac{(n+k-1)!}{n!\cdot(k-1)!} \end{align} \tag{2}
Più avanti sarà fornita una semplice spiegazione della formula (2).
Simulazione di un concorso
La nostra simulazione consiste in un'inversione del procedimento concorsuale e cioè, stabilito a priori il punteggio finale P_M da assegnare al concorrente, vogliamo generare delle quaterne (P_A, P_B, P_C, P_D), costituite dai punteggi parziali di ciascuna prova, la cui media esatta (cioè senza troncamenti o arrotondamenti) sia pari al punteggio finale P_M.
Esempio pratico
Ad esempio scegliamo come punteggio finale 28{,}86.
L'equazione (1) in questo caso diventa:
\begin{aligned}P_A+P_B+ P_C+P_D&=4 \cdot P_M \\ &=4\cdot28{,}86 \\ &=115{,}44 \end{aligned} \tag{3}
L'equazione (3) ci dice che qualunque quaterna di punteggi parziali tali che la loro somma sia pari a 115{,}44 soddisfa il requisito della media.
Per ricondurci a un'equazione a variabili naturali moltiplichiamo ambo i lati dell'equazione per 100:
\begin{aligned} P'_A+P'_B+P'_C+P'_D=11544 \end{aligned} \tag{3} dove P'_i=100\cdot P_i per i=A,B,C,D sono numeri naturali che possono assumere un valore compreso fra 0 e 3000.
L'equazione lineare a variabili naturali (3) può essere vista come un problema di partizione di un intero (trovare cioè 4 numeri interi non negativi la cui somma sia pari a 11544, soggetti al vincolo P'_i \le 3000 ) o in termini di ripartire 11544 biglie in 4 contenitori o ancora come i possibili lanci di 4 dadi (con 3001 facce, da zero a 3000) la cui somma sia pari a 11544. Il numero delle soluzioni può essere calcolato ricorrendo al calcolo combinatorio e le soluzioni possono essere determinate ricorrendo ad algoritmi combinatori e ricorsivi. Ciò tuttavia non è lo scopo di questo articolo. A noi serve un metodo pratico da poter gestire anche manualmente.
Osserviamo, dunque, che una soluzione "banale" del problema è scegliere come punteggi parziali proprio la media voluta, cioè porre P_A=P_B=P_C=P_D=P_M=28{,}86.
Possiamo rappresentare questa situazione pensando alle prove come a dei contenitori e ai punteggi di ciascuna prova come a delle biglie contenute nei contenitori (v. fig.1).
Per comodità è utile ragionare con numeri interi (moltiplichiamo cioè per cento): 28{,}86 punti per noi corrispondono a 2886 biglie (in altre parole ciascun centesimo di punto corrisponde a una biglia).
Con in riferimento alla figura 1 è chiaro che possiamo spostare le biglie da un contenitore all'altro e cambiare, così, il punteggio parziale attribuito alle prove A, B, C e D senza che ciò modifichi il numero totale di biglie, cioè mantenendo invariata la media delle biglie nei quattro contenitori. Spostando le biglie posso pertanto abbassare o incrementare il punteggio di una prova rispetto alla media.
Possiamo procedere in questo modo: estraiamo dai contenitori un certo numero di biglie e per semplicità estraiamo da ogni contenitore lo stesso numero di biglie. Se ad esempio togliamo da ciascun contenitore 2 biglie si presenterà la situazione raffigurata in figura 2.
Così facendo avrò tolto dai contenitori 8 biglie (v. fig.3) e quindi avrò a disposizione 8 punti da distribuire a piacimento nei quattro contenitori.
Se ad es. ridistribuiamo le otto biglie mettendone una nel contenitore A, una nel contenitore B, due nel contenitore C e quattro nel contenitore D, la situazione sarà quella raffigurata in figura 4.
In questo modo avremo una nuova quaterna di punteggi parziali P_A=28{,}85, P_B=28{,}85, P_C=28{,}86 e P_D=28{,}88 mentre il punteggio finale, cioè la media dei punteggi, legata alla somma delle biglie che rimane invariata, si manterrà uguale a P_M=(28{,}85+28{,}85+28{,}86+28{,}88):4=11544:4=28{,}86.
Considerazioni
Facciamo alcune riflessioni:
- dall'esempio è chiaro che posso generare quaterne diverse dei punteggi parziali semplicemente distribuendo in modo diverso le 8 biglie fra i 4 contenitori;
- il numero di biglie che all'inizio del procedimento estraggo da ciascun contenitore fissa il punteggio parziale minimo, P_{min}. Prima ho estratto 2 biglie da ciascun contenitore, per cui se successivamente nel ridistribuire le 8 biglie non mettessi in uno dei contenitori, ad es. A, nessuna delle 8 biglie, il punteggio P_A sarebbe il più basso dei punteggi e sarebbe pari a 28{,}84. Ribaltando il ragionamento si evince che il numero delle biglie da togliere da ciascun contenitore lo posso scegliere in funzione del punteggio parziale minimo che voglio avere;
- più biglie tolgo e maggiore sarà la possibilità di aumentare la variabilità della quaterna dei punteggi parziali, nel senso che potrò ottenere scarti maggiori fra i punteggi parziali e la media;
- per calcolare le varie quaterne dei punteggi parziali basta porre l'attenzione sulle biglie estratte da ridistribuire: tutti i modi diversi in cui riesco a distribuire le 8 biglie nei quattro contenitori, daranno vita a quaterne di punteggi parziali la cui media sarà sempre la stessa. Matematicamente i possibili modi in cui posso ridistribuire le 8 biglie saranno la soluzione dell'equazione: \begin{aligned} x_1+x_2+x_3+x_4=8 \end{aligned} \tag{4} con x_i per i=1,2,3,4 interi non negativi, cioè x_i \in [0..8] ; l'equazione (4) è un caso particolare dell'equazione generale (1) con k=4 e n=8;
- i punteggi parziali (P_A, P_B, P_C, P_D) si ottengono sommando al punteggio minimo P_{min} le soluzioni dell'equazione (4), cioè: \begin{aligned} P_j=P_{min}+x_i \end{aligned} per i=1,2,3,4 e j=A,B,C,D. Possiamo rappresentare il nostro esempio in forma tabellare (si potrà ricorrere per praticità anche ad un foglio di calcolo).
| P_A | P_B | P_C | P_D | |
| P_{min} | 28,84 | 28,84 | 28,84 | 28,84 |
| QUATERNA | 1 | 2 | 2 | 4 |
| P_{min} + QUATERNA | 28,85 | 28,86 | 28,86 | 28,88 |
Al cuore del problema
Il nocciolo del problema è, pertanto, determinare le soluzioni dell'equazione (4) ovverosia trovare i modi in cui possiamo ottenere il numero 8 sommando quattro numeri interi non negativi o, in latri termini, determinare i modi in cui posso distribuire le 8 biglie nei 4 contenitori. Per fare ciò possiamo ricorrere a un ausilio grafico conosciuto in matematica combinatoria come metodo "palline e barre" (chiamato anche "bastoni e pietre", "stelle e barre" e "punti e divisori").
Mettiamo in fila le nostre otto biglie e per rappresentare la ripartizione "iniziale" nei quattro contenitori, utilizziamo 3 barre interposte alle biglie come in figura 5. Si noti che il numero di biglie da utilizzare è pari al numero di biglie estratte dai contenitori (nel nostro esempio n=8) mentre il numero di barre necessarie è pari al numero dei contenitori meno uno, (k-1=4-1=3).
La figura 5 mostra la rappresentazione tramite biglie e barre della quaterna (2, 2, 2, 2) che sommata a P_{min} porta, come detto in precedenza, alla soluzione "banale" in cui i punteggi parziali sono pari al punteggio finale.
Con in mente la fig. 5 è facile comprendere che i possibili modi di ripartire le otto biglie nei quattro contenitori, si possono facilmente ottenere spostando la posizione delle barre. Spostiamo ad esempio l'ultima barra fra le prime due biglie (v. fig. 6).
Il risultato sarà quello mostrato in fig. 7 che corrisponde alla quaterna (1, 1, 2, 4) ovverosia alla ridistribuzione delle biglie che realizza la configurazione finale già vista in fig. 4.
Abbiamo, così, a disposizione un metodo facile, grafico e pratico per ottenere tutte le possibili quaterne. In altre parole le soluzioni dell'equazione (4) si ottengono spostando le barre e ponendo x_1 uguale al numero di palline prima della prima barra, x_2 uguale al numero di palline fra la prima e la seconda barra, x_3 uguale al numero di palline fra la seconda e la terza barra e infine x_4 uguale al numero di palline dopo l'ultima barra.
Con questo metodo spostando opportunamente le barre è possibile generare anche quaterne contenenti lo zero. Per comodità sostituiamo le biglie con delle stelle. Possiamo ad esempio generare le seguenti quaterne:
\begin{aligned}|★★|★★★★|★★ \iff (0, 2, 4, 2) \end{aligned}
\begin{aligned} |★★||★★★★★★ \iff (0, 2, 0, 6) \end{aligned}
Seconda digressione matematica
Il numero di possibili quaterne è dato dalla formula (2) sostituendo n=8 e k=4:
\binom{8+4-1}{4-1}=\binom{11}{3}=\frac{11!}{8!\cdot3!}=\frac{9\cdot10\cdot11}{6}=165
Il metodo delle stelle e delle barre ci fornisce anche una facile spiegazione della formula (2). Se infatti pensiamo all'insieme delle otto stelle e delle tre sbarre come a undici possibili differenti posizioni (v. fig. 8) occupabili da tre indistinguibili barre (o da otto indistinguibili stelle) si comprende che il numero delle quaterne è pari ai modi in cui posso combinare le tre barre negli undici posti (o le otto stelle negli undici posti), cioè al numero delle combinazioni semplici di 11 elementi di classe 3 (o di 11 elementi di classe 8) che è pari a \binom{11}{3}=165 (o \binom{11}{8}=165). Generalizzando, poiché il numero di posizioni è pari a n+k-1 (come detto in precedenza le stelle sono n e le barre sono k-1) e il numero di barre è k-1 (o il numero di stelle è pari a n) si ottiene la formula (2).
Allarghiamo l'orizzonte
Con lo stesso ragionamento portato avanti per la simulazione dei punteggi parziali, basta partire dal valore del punteggio parziale, es. P_A, prendere in considerazione tanti contenitori quanti sono i commissari, estrarre da ciascun contenitore un prefissato numero di biglie e ridistribuire le biglie estratte col metodo delle stelle e delle barre.
Per chiarire riprendiamo l'esempio di prima. Supponiamo che i commissari siano sette (cioè l=7 ) e che si voglia simulare il loro voto: vogliamo cioè ottenere una sequenza di 7 voti, una settina, la cui media sia pari a P_A=28{,}85. In analogia a quanto detto prima, possiamo immaginare di avere 7 contenitori in ognuno dei quali ci sono 2885 biglie (moltiplichiamo per cento per poter lavorare con interi). Scegliamo di estrarre da ciascun contenitore tre biglie. Ciò, se ricordate, equivale a fissare un voto minimo pari a 28{,}82 (poiché 2885-3=2882). Avremo così a disposizione 7 \times 3=21 biglie da ripartire col metodo delle stelle (che ricordiamo saranno pari al numero delle biglie) e delle barre (che saranno pari a sei, cioè al numero dei commissari meno uno). Qualunque disposizione delle barre darà vita ad una settina valida. Una settina interessante è quella che si ottiene incrementando di una biglia alla volta il numero di biglie da rimettere nei contenitori: partendo ad es. da sinistra e muovendosi verso destra, immaginiamo di mettere zero biglie nel primo contenitore, una nel secondo, due nel terzo, ... sei nel settimo contenitore. Col metodo delle stelle e delle barre si ottiene la seguente configurazione:
\begin{aligned}|★|★★|★★★|★★★★|★★★★★|★★★★★★ \end{aligned}
che equivale alla settina (0, 1, 2, 3, 4, 5, 6).
Ma perché è interessante? Per capirlo simuliamo i punteggi attribuiti dai sette commissari sommando al punteggio P_{A_{min}}=28{,}82 la settina. Ci serviamo, come prima, di una tabella.
| \bm{P_1} | \bm {P_2} | \bm{P_3} | \bm{P_4} | \bm{P_5} | \bm{P_6} | \bm {P_7} | |
| P_{A_{min}} | 28,82 | 28,82 | 28,82 | 28,82 | 28,82 | 28,82 | 28,82 |
| SETTINA | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| Punteggi | 28,82 | 28,83 | 28,84 | 28,85 | 28,86 | 28,87 | 28,88 |
| Scarti | -3 | -2 | -1 | 0 | +1 | +2 | +3 |
L'ultima riga della tabella mostra gli scarti, ossia la differenza fra i punteggi di ciascun commissario e la media. Si può vedere che ad ogni punteggio superiore alla media (es. P_5) corrisponde un punteggio sotto la media (es. P_3) di scarto uguale in valore assoluto ma di segno opposto. In altri termini ridistribuire le biglie aggiungendo via via a ciascun contenitore una biglia in più, significa generare una sequenza di punteggi perfettamente simmetrica rispetto al punteggio centrale P_4=28{,}85 (che è pari alla media) dove ogni punteggio a sinistra è bilanciato da un corrispondente punteggio a destra.
Codice python
Ed ecco un programma in linguaggio python che simula la generazione di una graduatoria secondo l'algoritmo illustrato in precedenza.
import random
# Funzione per generare una quaterna di punteggi
def genera_quaterna(punteggio_finale, punteggio_minimo):
# Calcola il totale delle "biglie" (unità discrete) in base al punteggio finale
totale_biglie = int(punteggio_finale * 400)
# Calcola il valore minimo (base_min) in biglie per ogni elemento della quaterna
base_min = int(punteggio_minimo * 100)
# Determina quante biglie sono da redistribuire dopo aver assegnato il minimo a ciascun elemento
biglie_da_redistribuire = totale_biglie - base_min * 4
# Se il punteggio minimo richiede più biglie di quante disponibili, solleva un'eccezione
if biglie_da_redistribuire < 0:
raise ValueError("Il punteggio minimo è troppo alto rispetto al punteggio finale.")
# Inizializza i punteggi con il valore minimo
punteggi = [base_min] * 4
# Redistribuisci le biglie rimanenti in modo casuale, rispettando il limite massimo di 30.00 punti
while biglie_da_redistribuire > 0:
indice = random.randint(0, 3)
if punteggi[indice] + 1 <= 3000: # Limite massimo in biglie (30 punti)
punteggi[indice] += 1
biglie_da_redistribuire -= 1
# Converti i punteggi da biglie a valori decimali
punteggi_decimali = [p / 100 for p in punteggi]
# Calcola la media intera dei punteggi
media_intera = sum(punteggi) / 4 / 100
return punteggi_decimali, media_intera
# Funzione per generare una distribuzione casuale dei punteggi per un numero arbitrario di votanti
def genera_distribuzione_per_punteggio(punteggio, punteggio_minimo, num_votanti):
# Calcola il totale delle biglie in base al punteggio e al numero di votanti
totale_biglie = int(punteggio * 100 * num_votanti)
base_min = int(punteggio_minimo * 100)
biglie_da_redistribuire = totale_biglie - base_min * num_votanti
# Controllo di validità: il punteggio minimo non deve superare il totale disponibile
if biglie_da_redistribuire < 0:
raise ValueError("Il punteggio minimo è troppo alto rispetto al punteggio finale.")
# Inizializza la distribuzione con il valore minimo per ciascun votante
distribuzione = [base_min] * num_votanti
# Redistribuisci le biglie rimanenti in modo casuale
while biglie_da_redistribuire > 0:
indice = random.randint(0, num_votanti - 1)
if distribuzione[indice] + 1 <= 3000: # Limite massimo in biglie (30 punti)
distribuzione[indice] += 1
biglie_da_redistribuire -= 1
# Restituisci la distribuzione come valori decimali
return [d / 100 for d in distribuzione]
# Funzione per stampare una linea orizzontale di lunghezza specificata
def stampa_linea(lunghezza):
print("-" * lunghezza)
# Inizio del programma: input da tastiera
try:
# Input del numero di candidati
n = int(input("Inserisci il numero di candidati da valutare: "))
assert n > 0, "Il numero di candidati deve essere maggiore di 0."
# Input del punteggio finale desiderato
punteggio_finale = float(input("Inserisci il punteggio finale desiderato (P_M) compreso tra 0 e 30: "))
assert 0 <= punteggio_finale <= 30, "Il punteggio finale deve essere compreso tra 0 e 30."
# Input del punteggio minimo
punteggio_minimo = float(input("Inserisci il punteggio minimo per ogni prova (compreso tra 0 e P_M): "))
assert 0 <= punteggio_minimo <= punteggio_finale, "Il punteggio minimo deve essere compreso tra 0 e P_M."
# Input del numero di votanti
num_votanti = int(input("Inserisci il numero di votanti: "))
except ValueError:
print("Errore: Inserisci numeri validi con un punto per i decimali (es. 28.86).")
exit()
# Genera e stampa la distribuzione per ciascun candidato
try:
# Determina la lunghezza della linea separatrice
lunghezza_linea = 53 + 7 * num_votanti
riga_index = 0
# Stampa l'intestazione della tabella
header = ["N.O.", "CANDIDATO "] + [f" M{i+1:3} " for i in range(num_votanti)] + ["Somma ", "Media ", "Punti |"]
riga_intestazione = "| ".join(header)
lunghezza_linea = max(lunghezza_linea, len(riga_intestazione))
stampa_linea(lunghezza_linea)
print(riga_intestazione)
stampa_linea(lunghezza_linea)
# Generazione della distribuzione per ciascun candidato
for candidato in range(n):
if candidato == 0:
punteggio_corrente = punteggio_finale
punteggio_minimo_corrente = punteggio_minimo
else:
# Calcola dinamicamente nuovi valori per il punteggio corrente e il minimo
differenza = punteggio_finale - punteggio_minimo_corrente
nuovo_punteggio_minimo = max(18, punteggio_finale - random.uniform(0.01, 0.05) - differenza)
punteggio_corrente = max(18, punteggio_corrente - random.uniform(0.01, 0.05))
punteggio_minimo_corrente = nuovo_punteggio_minimo
# Genera la quaterna e la distribuzione
quaterna, media_calcolata = genera_quaterna(punteggio_corrente, punteggio_minimo_corrente)
for i, punteggio in enumerate(quaterna):
riga_index += 1
distribuzione = genera_distribuzione_per_punteggio(punteggio, punteggio_minimo_corrente, num_votanti)
media_della_distribuzione = sum(distribuzione) / len(distribuzione)
# Stampa una linea di separazione tra blocchi
if riga_index == 1 or (riga_index - 1) % 4 == 0:
stampa_linea(lunghezza_linea)
# Stampa le righe dei punteggi
if i == 0:
riga = f"{candidato + 1:3} | Candidato {candidato + 1:3} a)| {' | '.join([f'{d:.2f}' for d in distribuzione])} | {(int(sum(distribuzione) * 100) / 100):.2f} | {media_della_distribuzione:.2f} | {punteggio_corrente:.2f} |"
else:
riga = f" | {chr(97 + i)})| {' | '.join([f'{d:.2f}' for d in distribuzione])} | {(int(sum(distribuzione) * 100) / 100):.2f} | {media_della_distribuzione:.2f} | |"
lunghezza_linea = max(lunghezza_linea, len(riga))
print(riga)
# Stampa l'ultima linea di separazione
stampa_linea(lunghezza_linea)
except ValueError as e:
print(f"Errore: {e}")