Quesito con la Susi n. 940

C'è chi ha o pretende di avere una collezione di farfalle o francobolli, e chi, come Gianni…

I quindici cartoncini sulla lavagna sono l'esca usata da Gianni per attirare Susi nella trappola.

Quali sono i tre numeri che moltiplicati fra loro danno la somma degli altri dodici?

Gianni spiega, riferendosi alla prima lavagna su mostrata:

Ci sono tutti i numeri da 1 a 15. Bisogna spostarne tre in modo che il loro prodotto sia uguale alla somma degli altri dodici. In questo caso gli altri dànno 105.

Susi ha capito al volo cosa vuole veramente da lei Gianni e quindi fa un altro esempio per dimostrarglielo.

Qui la somma è 99 e 1 per 9 per 11 dà 99.

Quindi Gianni le chiede di trovare un'altra tripletta di numeri e le dà un piccolo aiuto dicendo che uno dei tre numeri è il doppio di «uno degli altri due dispari». Cioè abbiamo due numeri dispari e un numero pari che è il doppio di uno degli altri due.

Ricerca casuale

La primavera si avvicina, ma facciamo lavorare il processore più del necessario in questo modo: peschiamo a caso (a pseudocaso…) tre tessere e vediamo se sono quelle giuste… Paradossalmente questo modo di cercare la soluzione potrebbe dare un risultato prima della ricerca esaustiva “metodica”, visto che questa ci porta alla soluzione in un numero di tentativi dipendente dal modo in cui esploriamo le soluzioni.

Tuttavia dobbiamo scartare le soluzioni già date (3,5,7 e 1,9,11). Se ci sono più di tre soluzioni, capitiamo male: avendo estratto le tessere a caso, come facciamo a sapere di averle provate tutte? Dovremmo contarle badando a non contare triplette di tessere già considerate. Trovata una soluzione, potremmo almeno controllare che uno dei numeri sia il doppio di un altro (che dovrà essere dispari).

Ma non voglio mettere nemmeno questo tipo di “intelligenza” nel codice. Quindi, ricapitolando: prendi tre tessere a caso, controlla che la tripletta non sia una delle soluzioni note, verifica che sia una soluzione. Se lo è, termina la ricerca.

Quando leggerete il risultato dovrete verificare che un numero sia il doppio di un altro dispari presente nella tripletta… Se non sarà così, vorrà dire che il programma ha trovato un'altra soluzione che non è però quella che aveva in mente Gianni. Dovrete inserirla tra le soluzioni note ed eseguire di nuovo il programma… Potreste modificare il codice in modo che lo faccia da sé, mettendo tutto in un ciclo; ma attenzione: una volta aggiunta l'ultima possibile soluzione, il ciclo interno non uscirà più! Quindi metterete un limite massimo al numero di tentativi, assumendo che superare quel limite voglia dire che non esistono altre soluzioni oltre a quelle date e quelle già trovate.

Il programmino (per il quale non spreco un gist su github) questa volta l'ho fatto in Perl6, fresco di installazione (implementazione rakudo). Non ero un guru del Perl5¹, e non lo sono del Perl6, che è un linguaggio diverso² e direi, da quello che ho visto, anche molto, molto, molto interessante³; traduzione: forse perlisti incalliti riscriverebbero il mio codice in modo più perloso, scuotendo il capo contrariati e offesi dalla mia ingenuità perlesca.

my $r = 1..15;
my $tsum = [+] $r;
my ($a, $b,$c) = 0,0,0;
my @sols := (3,5,7), (1,9,11);
my $tentativi = 0;
while (($tsum-$a-$b-$c) != ($a * $b * $c)) ||
        (so ($a,$b,$c).sort eqv @sols.any)
{
    ($a, $b, $c) = $r.roll(3);
    $tentativi++;
}
print "$tentativi: $($tsum-$a-$b-$c) = $a * $b * $c = $($a*$b*$c)\n";

(Il codice è evidenziato secondo la sintassi del Perl e non del Perl6 perché non ho — ancora — un evidenziatore di sintassi per il Perl6. Si vede per esempio sul so che sarebbe un operatore da mettere in grassetto.)

Di seguito gli output di ripetute (a mano) esecuzioni:

428: 98 = 1 * 7 * 14 = 98
21: 98 = 14 * 7 * 1 = 98
264: 98 = 7 * 14 * 1 = 98
420: 98 = 7 * 14 * 1 = 98
652: 98 = 14 * 1 * 7 = 98
2155: 98 = 1 * 14 * 7 = 98
1612: 98 = 1 * 14 * 7 = 98
70: 98 = 7 * 1 * 14 = 98
380: 98 = 1 * 14 * 7 = 98

Il fatto che le righe siano tutte diverse significa che ad ogni esecuzione il seme del generatore casuale è diverso. Alle volte è una cosa buona, altre volte ci piacerebbe poter ottenere sempre la stessa sequenza; ho provato ad impostare il seme con srand ma non ho ottenuto l'effetto che volevo.

A parte ciò, possiamo dire di essere inciampati nella soluzione, che dunque è 1, 7, 14.

Divagazioni e soluzione a mano

Il numero di triplette (più propriamente una combinazione di lunghezza tre) formabili con 15 simboli si ottiene con il classico coefficiente binomiale.

\[ {{15}\choose{3}} = 455 \]

Perciò una ricerca esaustiva farebbe 455 tentativi nel peggiore dei casi, cioè quando la soluzione è proprio l'ultima combinazione verificata. Se considerassimo solo quelle combinazioni che verificano la “condizione di Gianni”, il processore avrebbe ancora meno lavoro, posto che generiate in partenza solo le combinazioni che la verificano⁴.

Avrebbe così poco lavoro che in effetti il processore potreste essere voi. Infatti la soluzione manuale potrebbe essere questa: visto che un numero B deve essere il doppio di un altro A (dispari), questo A non può essere maggiore di 7. Quindi A potrà essere solo 1, 3, 5 o 7, e B sarà rispettivamente 2, 6, 10 e 14. L'altro numero, C, deve essere dispari e diverso da A — purtroppo abbiamo ben 7 scelte da verificare, che vanno a moltiplicare quelle per la coppia dipendente A e B. Ci rimangono solo 28 (4×7) possibilità… Si può fare… Però è noioso. Possiamo introdurre una considerazione analitica:

\[ \frac{n(n+1)}{2} - (a + 3b) = 2ab^2 \]

Con n = 15. Visto che il terzo numero è il doppio di uno già scelto, ci bastano due incognite. Fissata b, vogliamo scoprire a. Deve valere:

\[ a(b) = \frac{120 - 3b}{2b^2+1} \]

Quindi anche la scelta di a (che prima chiamavo C, tanto per confondervi), una volta fissato b (cioè A…) non può essere qualunque tra le 7 possibilità che abbiamo contato. In pratica dobbiamo fare al massimo 4 tentativi, quelli dovuti alla scelta di b (1, 3, 5, 7).

a(1) = 39 (> 15)
a(3) = non è intero
a(5) = non è intero
a(7) = 1

Quindi A è 7, B sarà 14 e C, infine, sarà 1.

---

1. Un linguaggio che mi è sempre piaciuto e che ho usato per diverse cose, ma sempre in modo “spartano”.↩

2. La filosofia del Perl mi sembra preservata, e c'è anche una somiglianza ovvia; ma lo considero un linguaggio diverso come il C++ è diverso dal C, pur assomigliandosi.↩

3. Mi interessa molto, per esempio, questa caratteristica, ma anche quelli che ormai sono i classici, per modo di dire, dei linguaggi “moderni”: costrutti “pronti all'uso” per la concorrenza, orientamento agli oggetti, le funzioni come oggetti di prima classe, e quindi la possibilità di usare uno stile funzionale.↩

4. Se le generate tutte dovete sempre fare un'operazione di verifica delle “condizioni di Gianni”; allora tanto vale controllare direttamente se è una soluzione… «Allora tanto vale» per modo di dire, perché se la verifica della soluzione è molto più dispendiosa della verifica delle condizioni di Gianni, allora conviene fare prima il controllo delle condizioni di Gianni. Il problema non si pone proprio se in partenza generate solo e soltanto combinazioni che soddisfano le condizioni di Gianni (in tal caso non dovete controllarle: sapete già per costruzione che sono soddisfatte).↩