Il problema del mugnaio di Dudeney

Ho scoperto da poco Rudi matematici. Quello che è e non è lo potete vedere da voi; per me si tratta solo di un'altra possibile fonte per proseguire la “tradizione” iniziata con Un quesito con la Susi.

Vediamo L'enigma del Mugnaio, un altro puzzle di Dudeney; per la verità possiamo trovare tutti i suoi Canterbury Puzzles su Gutenberg.

Se vi interessa particolarmente la possibilità di usare la programmazione e il cervello per risolvere dei problemi, e se cercate sfide e passatempi per la mente, potete iscrivervi a Project Euler — ma di questo non troverete traccia qui: ognuno per sé e Babbage per tutti… (o forse qualcosina, magari… ma più probabilmente su uno dei blog in inglese, e sempre in un futuro che non so quando diventerà presente).

Togliendo un po' di colore, il quesito del mugnaio può essere riformulato in questi termini: posto che ciascuna lettera rappresenti una cifra, trovare la permutazione ABCDEFGHI delle 9 cifre (da 1 a 9) che sia a “distanza” minima da una permutazione iniziale data, in modo che valga valga A×BC = I×GH = DEF.

La permutazione iniziale è 728196345. La “distanza” tra due permutazioni è data dal numero minimo di scambi (tra due cifre, ovvero tra due sacchi) necessari per poter passare da una permutazione all'altra.

Approcciamo il problema in modo diretto usando la forza bruta, come consuetudine (cioè non cerchiamo una soluzione raffinata ed efficiente).

Per prima cosa generiamo tutte le permutazioni e ci teniamo solo quelle che soddisfano la relazione A×BC = I×GH = DEF. Dopodiché calcoliamo la distanza di ognuna di queste dalla permutazione iniziale e prendiamo quella che ha distanza più piccola rispetto alle altre trovate.

E se trovassimo 2 (o più) permutazioni con la stessa distanza minima? La soluzione non sarebbe unica… ma il problema dice: «Avendo il Mugnaio richiesto il minimo sforzo possibile, ossia di spostare il minor numero possibile di sacchi, la soluzione è unica». Sarebbe da dimostrare, anche se magari è banale. Prendiamolo per buono…

L'idea più complicata è quella relativa alla distanza tra due permutazioni¹. Poiché muoviamo i sacchi scambiandoli di posto, è naturale pensare ad un algoritmo di ordinamento che operi proprio facendo scambi². Ma algoritmi diversi possono raggiungere l'ordinamento desiderato tramite un numero diversi di scambi. Per essere sicuri che la soluzione non dipenda in modo critico dalla scelta dell'algoritmo di ordinamento, dovremmo dimostrare che gli algoritmi idonei preservino l'“ordine delle distanze”, cioè una permutazione P1 “più vicina” rispetto ad una qualunque altra permutazione P2, resterà tale anche usando un altro algoritmo³. (Anche in questo caso non ho nessuna intenzione di dimostrarlo: assumiamo che gli algoritmi idonei abbiano questa proprietà e perciò la soluzione trovata non dipenderà dall'algoritmo scelto.)

Volendo essere pignoli, nel testo del problema c'è un “vincolo” piuttosto ambiguo:

spostare i nove sacchi con il minimo sforzo possibile

Sarei tentato di dire che il «minimo sforzo possibile» (with as little trouble as possible) possa essere interpretato così: in ogni scambio, lo spostamento dei sacchi interessati deve essere minimo. Ciò significherebbe scambiare solo sacchi adiacenti. Se cerchiamo di dare una interpretazione fisica alla parola “sforzo”, non è affatto immediato essere certi del fatto che questo modo di procedere minimizzi lo “sforzo” totale⁴. Molto probabilmente, però, il problema ci sta solo ribadendo che è necessario fare il minor numero di scambi possibile.

Con il vincolo dei sacchi adiacenti arriviamo alla tau-distanza di Kendall. In questo caso il cuore della nostra soluzione sarà l'algoritmo bubble sort⁵. Ci basterà contare gli scambi fatti per ottenere la permutazione iniziale⁶.

Senza il vincolo dei sacchi adiacenti, invece, usiamo l'ordinamento per selezione; anche in questo caso contiamo gli scambi fatti per ottenere la permutazione di partenza. Questo algoritmo in pratica “cerca” gli elementi giusti da mettere in ciascuna posizione ed è quello che fornisce le “distanze” più piccole — cioè il numero minore di scambi da fare per ottenere la permutazione di partenza (anche in questo caso, nessuna dimostrazione…). Per via delle assunzioni fatte, non ci aspettiamo che l'uso di questo algoritmo ottimale (per il problema dato) cambi la soluzione trovata.

Soluzione e soluzioni

La soluzione è:

     2*78 = 156 = 39*4

È la stessa usando i due algoritmi (bubble e selection); solo che in un caso (bubble) il numero di scambi fatti è 7, nell'altro è 3.

Le permutazioni che soddisfano A×BC = I×GH = DEF sono appena 4; nell'ordine secondo la tau-distanza di Kendall (d1), sono:

2*78 = 156 = 39*4; d1=7, d2=3    (1) P4
6*29 = 174 = 58*3; d1=15, d2=5   (2) P3
3*58 = 174 = 29*6; d1=20, d2=6   (2) P2
4*39 = 156 = 78*2; d1=28, d2=6   (1) P1

Il valore d2 è la “distanza” ottenuta con l'ordinamento per selezione che, come si vede, dà sempre un numero di scambi minore e perciò lo possiamo considerare ottimale⁷. La soluzione con distanza minima è unica in entrambi i casi, ma ci sono due permutazioni che hanno d2 uguale… Se il problema avesse detto «with as big trouble as possible», avremmo avuto due soluzioni diverse usando la d2, ma un'unica soluzione usando la d1…

Nota: abbiamo 4 permutazioni diverse. Nell'enigma, però, c'è una simmetria: possiamo portare i membri di destra a sinistra e viceversa, ottenendo di fatto le stesse equazioni (le etichette nell'elenco sopra raggruppano questi casi), per cui potremmo dire che, date le nove cifre (1-9) da usarsi una e una sola volta, esistono solo 2 modi per risolvere questo problema: trovare 5 numeri, di cui 2 di una sola cifra, due di due cifre e uno di tre cifre, tali che il prodotto ottenuto moltiplicando un numero a singola cifra per un numero a due cifre sia uguale al prodotto ottenuto moltiplicando il restante numero a cifra singola per il restante numero a due cifre, e che questi prodotti siano a loro volta uguali al numero di tre cifre.

Ma nel problema dobbiamo spostare sacchi with as little trouble as possible: la posizione conta e la permutazione 439156782 è diversa da 278156394. Ciò è evidente anche dal fatto che le permutazioni “simmetriche” (secondo la relazione matematica) hanno distanze (dalla permutazione di partenza) diverse tra loro. Tuttavia, potremmo girare intorno ai sacchi in modo da avere il sacco contrassegnato dal 7 a destra invece che a sinistra. Leggendo da sinistra verso destra, la permutazione iniziale allora sarebbe 543691827. Il programma ci dà i seguenti risultati (con l'aggiunta delle etichette per raggruppare permutazioni diverse che portano alle stesse equazioni e ordinando per d1):

4*39 = 156 = 78*2; d1=8, d2=6     (1) P1
3*58 = 174 = 29*6; d1=16, d2=8    (2) P2
6*29 = 174 = 58*3; d1=21, d2=7    (2) P3
2*78 = 156 = 39*4; d1=29, d2=5    (1) P4

bubble
         8: 4*39 = 156 = 78*2     (1)
selection
         5: 2*78 = 156 = 39*4     (1)

La cosa più interessante da notare è che ora d1 e d2 non concordano su quale sia la permutazione più vicina, ma in realtà forniscono la stessa “equazione”, la (1). Con la d1 (bubble sort) addirittura una è la più vicina e l'altra la più lontana. È accaduto lo “scavallamento” che avevamo assunto non essere possibile! Infatti d₁(P₀, P₁) < d₁(P₀, P₄) ma d₂(P₀, P₁) > d₂(P₀, P₄) (ovvero, ordinando per d1 non otteniamo quanto otterremmo ordinando per d2)… Questo scavallamento non rovina il risultato; caso fortuito o si può dimostrare che…?

Il codice

Di seguito il codice. Questa volta ho usato il C++11 (senza troppe pretese).

---

1. Stiamo cercando una definizione (operativa) di distanza tra permutazioni. Con questa definizione, di ogni permutazione soddisfacente le relazioni calcoleremo la distanza dalla permutazione iniziale e prenderemo infine quella “più vicina”. La scelta della definizione di distanza può essere cruciale. Indicando con d_A(1) l'“A-distanza” della permutazione 1 dalla permutazione “base” e con d_B(1) la “B-distanza”, senza imporre niente altro potremmo benissimo avere che d_A(1) < d_B(1). Avremmo cioè un risultato differente. Il problema suggerisce che il calcolo della distanza debba ottenersi contando gli scambi di sacchi. Inoltre, per stare tranquilli, dovremmo dimostrare che la scelta della “distanza” non alteri l'ordinamento. Ovvero, se è vero che d_A(1) < d_A(2), allora dovrà essere pure vero che d_B(1) < d_B(2) (per qualunque coppia di permutazioni 1 e 2). Tutte le “distanze” che garantiscono ciò possono essere considerate equivalenti.↩

2. Non sono famosi per essere gli algoritmi più efficienti; in questo caso però mettiamo l'efficienza da parte perché è richiesto dal problema: usare algoritmi che portino alla permutazione iniziale (“ordinata”) con tecniche diverse dallo scambio tra gli elementi non ci permetterebbe di avere una definizione di distanza basata unicamente sul numero di scambi.↩

3. Gli algoritmi che per noi definiscono operativamente la distanza “allungano” o “accorciano” lo “spazio” (dove ogni permutazione è un punto) senza far “scavallare” i punti (se P1 era più vicina di P2, resterà tale anche con l'altra distanza). Credo che si possa dire che gli algoritmi definiscono spazi metrici uniformemente isomorfici; ma non sono affatto sicuro che sia corretto. Comunque spero che almeno il concetto sia chiaro. In pratica a noi non interessa trovare l'algoritmo ottimale, cioè quello che veramente fa il minor numero possibile di scambi: ci basta assumere (perché non lo dimostriamo…) che tutta la famiglia di algoritmi possibili dia comunque la distanza minima in corrispondenza della stessa permutazione, quella che si trova appunto alla distanza minima. (P.es., per certe permutazioni P1, P2, P3… l'algoritmo ottimale eseguirà 3, 4, 5… scambi. Un algoritmo subottimale per le stesse permutazioni P1, P2, P3… eseguirà 6, 8, 10… scambi. In tutte e due i casi, la permutazione P1 è quella più “vicina” a quella iniziale, la P2 la seconda più vicina e così via.)↩

4. Per scambiare di posto due sacchi adiacenti compiamo il lavoro 2W + 2s; allora il lavoro complessivo si può ottenere moltiplicando il numero di scambi N per questo valore: N(2W + 2s). Il valore s rappresenta il lavoro fatto per vincere l'attrito statico per “iniziare” lo spostamento di un sacco, mentre W tiene conto di quello contro l'attrito dinamico per uno spostamento di una sola unità-sacco (distanza). Come possiamo stimare il lavoro fatto per spostare due sacchi non adiacenti? Ignoriamo di nuovo il lavoro fatto per disallineare i due sacchi, in modo da poterli far scorrere e poi rimetterli in linea (naturalmente potremmo anche sollevarli; il discorso è un po' diverso ma il ragionamento può essere rifatto in maniera simile). Supponiamo che il lavoro sia 2nW, dove n è la distanza (misurata in numero di sacchi) tra due postazioni. Supponiamo anche che grazie a questo “scambio lungo” riusciamo ad ottenere l'ordine desiderato in N − k scambi, di cui N − k − 1 sono corti (tra sacchi adiacenti). Il lavoro in questo caso sarà (N − k − 1)(2W + 2s) + 2nW + 2s. Facendo la differenza troviamo (se non ho fatto banali errori) 2W(k − n + 1) + 2sk. Se questo numero è positivo, significa che aver fatto uno solo “scambio lungo” ci ha permesso di risparmiare “fatica” (less trouble). Quel numero è certamente positivo se k − n + 1 ≥ 0, cioè se il numero k di scambi risparmiati è maggiore o uguale alla distanza (in numero di sacchi) tra i due sacchi dello “scambio lungo”. Questa distanza può essere al massimo 8. Per esempio se lo scambio di due sacchi distanti 2 (cioè c'è un sacco tra loro) ci facesse risparmiare almeno 2 scambi, allora avremmo fatto uno “sforzo” minore… secondo questa definizione “fisica” di sforzo.↩

5. Algoritmo di ordinamento a bolle, così chiamato perché i numeri più piccoli salgono passo dopo passo come se fossero bollicine… Non è l'algoritmo che fa il minor numero di scambi… Ma abbiamo assunto che usare un algoritmo subottimale non alteri il risultato.↩

6. Non sono famosi per essere gli algoritmi più efficienti; in questo caso però mettiamo l'efficienza da parte perché è richiesto dal problema: usare algoritmi che portino alla permutazione iniziale (“ordinata”) con tecniche diverse dallo scambio tra gli elementi non ci permetterebbe di avere una definizione di distanza basata unicamente sul numero di scambi.↩

7. Ordinando una lista di N numeri tutti fuori posto, l'algoritmo selection farà al massimo N scambi (ad ogni scambio c'è un numero che va al suo posto). Invece il bubble sort è tanto pittoresco quanto inefficiente (ma non è il più inefficiente…) e può aver bisogno di molti più scambi per portare una “bollicina” nella sua posizione naturale.↩