Quesito con la Susi n. 948

Nove minibus sono arrivati al capolinea e i generosi passeggeri decidono di lasciare una mancia agli autisti.

La mancia che ciascun passeggero lascia è di 10€. Deve essere stato un viaggio costoso e gli autisti devono aver guidato in modo davvero grazioso per meritarsi una mancia così generosa…

(L'immagine non si riferisce al problema ma ai primordi del linguaggio usato per calcolare la soluzione: il Fortran. Naturalmente il Fortran moderno è un linguaggio moderno, appunto; aggiungo che è anche molto bello e sottovalutato fuori dalla sua nicchia :-D)

Gianni chiede a Susi se sa dirgli quanti passeggeri sono arrivati a bordo dei nove minibus, sapendo che:

• i minibus portano al massimo 10 passeggeri;
• tutti i minibus ne avevano a bordo almeno quattro;
• su tre minibus c'era lo stesso numero di passeggeri mentre gli altri sei ne avevano tutti un numero diverso;
• tutti hanno dato una mancia di 10€ e le banconote sono state equamente divise tra gli autisti (tutti hanno avuto lo stesso numero di banconote da 10€)

In pratica abbiamo queste condizioni:

• y_i ∈ [4, 10] e quindi 36 ≤ n ≤ 90;
• $n = 3y_0 + \sum_{i=1}^{6} y_i$ (dove y_i con i > 0 è il numero di passeggeri nel minibus i-esimo, e 3y₀ è il numero di passeggeri nei tre minibus che hanno lo stesso numero y₀ di passeggeri);
• y_i ≠ y_j per i ≠ j ¹;
• $n \equiv 0 \pmod 9$.

Ricerca della soluzione

Per l'ennesima volta facciamo una ricerca esaustiva nello spazio dei valori possibili, verificando ogni volta se le condizioni su elencate sono soddisfatte. Per ogni “vettore” y soddisfacente quelle condizioni, abbiamo una possibile soluzione. Il numero dei vettori che soddisfano i vincoli deve essere uno, oppure no, a patto che l'n trovato sia lo stesso per ognuno dei “vettori soluzione”; se così non fosse, dovremmo dire che il problema non è ben posto e Susi non può determinare con sicurezza quanto gli chiede Gianni.

All'inizio avevo usato questa condizione:

• $n = 3x + \sum_{i=1}^{6} y_i$ (dove x è il numero di passeggeri in uno dei tre minibus con lo stesso numero di passeggeri, e 3x è quindi il numero totale dei passeggeri nei tre minibus).

Ma in questo modo troviamo diversi n. Nel codice il cambiamento di questa condizione in quella fornita prima si riflette nell'aver cambiato la riga

  .and. alldiff(y) &

in

  .and. alldiff([x,y]) &

Invece nell'elenco delle condizioni qui date ho preferito ribattezzare x in y₀ in modo da poter esprimere la condizione seguente (y_i ≠ y_j per i ≠ j) nello stesso modo. Nel codice x = y₀.

Il codice continua a scorrere i possibili “vettori”, senza fermarsi alla prima volta che uno soddisfa le condizioni; non è un problema se due diversi vettori soddisfano le condizioni, purché il numero complessivo dei passeggeri resti lo stesso; e questo è il motivo per cui memorizzo le diverse soluzioni trovate e scrivo n (e il “vettore”) solo se ho trovato un numero diverso — cosa che accade usando la seconda condizione come inizialmente l'avevo intesa.

L'output dell'esecuzione è circa questo (ho rimosso un po' di spazi):

      63
       7  7  7  10  9  8  6  5  4

Soluzione manuale

A noi interessa sapere n, che è dato dalla somma di sette numeri: 3y₀ e i restanti y_i. I vari y_i sono sette e tutti diversi. Una volta scelto y₀, ci rimangono sei numeri da assegnare agli altri y_i, ma l'ordine è indifferente perché $\sum_{i=1}^6 y_i$ sarà sempre uguale. Questa somma possiamo riscriverla così:
$$ \sum_{i=0}^6 y_i - y_0= \frac{10(10+1)}{2} - \frac{3(3+1)}{2} - y_0 = 49 - y_0 $$
Poi dobbiamo calcolare la somma totale addizionandogli 3y₀, per cui in realtà stiamo calcolando 49 + 2y₀.

Per y₀ abbiamo 7 possibili valori e quindi altrettante somme:

y0	49+2*y0
4	57
5	59
6	61
7	63
8	65
9	67
10	69

Di questi numeri solo il 63 è divisibile esattamente per 9. Quindi 63 è la soluzione.

---

1. Gianni dice «mentre gli altri sei [oltre i 3 che ne hanno un numero uguale tra loro] ne avevano tutti un numero diverso», e Susi ribadisce che «tra gli altri sei minibus dunque non ce ne sono due che avevano a bordo lo stesso numero di passeggeri»); io avevo interpretato così: i sei minibus avevano tutti un numero di passeggeri diverso tra loro, ma non necessariamente diverso dal numero dei passeggeri di uno dei tre minibus con lo stesso numero di passeggeri. Ma è ambiguo: quando Gianni dice «ne avevano tutti un numero diverso» intende diverso tra loro sei (in contrasto con il fatto che gli altri tre avevano lo stesso numero di passeggeri) o diverso dal numero di passeggeri portato da uno dei tre minibus? Susi però rimarca il fatto che deve valere la prima interpretazione e che perciò nessuno dei restanti sei («tra gli altri sei minibus dunque […]») minibus ha lo stesso numero di passeggeri di uno qualunque degli altri cinque. Cioè niente si dice, mi sembra, sul fatto che il numero di passeggeri di ogni minibus dei sei deve essere diverso anche dal numero di passeggeri portati da uno dei tre minibus con uguale numero di passeggeri. Ma se non si mette questa condizione non si trova una soluzione unica. Perciò alla fine l'ho aggiunta.↩