[BASE Cinque - Appunti di Matematica ricreativa]

Indovinello algoritmico

Domanda 1a.

Considerate i numeri da 1 a 6. Riuscite a disporli nelle seguenti caselle rispettando i segni di ordinamento scritti fra di loro?

figura

Domanda 1b.

Che ne dite di sistemare i numeri da 1 a 9 nelle seguenti caselle?

figura

Domanda 2.

Generalizziamo.

Dato un elenco di n numeri (tutti distinti tra di loro) e una serie di n caselle con segni di ordinamento inseriti fra loro, inventate un algoritmo che metta i numeri nelle caselle rispettando i segni.
Limitiamoci a carta e penna.

---

Grazie a Bruno per aver inviato questo problema al Forum - Indovinello algoritmico.

---

Nota storica

La prima pubblicazione a stampa del problema si trova in Anany Levitin, Maria Levitin, Algorithmic puzzles, 2011, col titolo di Number placement. Gli autori riferiscono che è stato pubblicato nel sito The Math Circle (www.themathcircle.org/researchproblems.php) nel 2010 ma io non sono riuscito a trovare tale sito web.

Il problema si trova anche nel libro Breve e universale storia degli algoritmi di Luigi Laura, docente di Machine Learning e Analisi dei Big Data alla Luiss e responsabile tecnico e scientifico delle Olimpiadi Italiane di Informatica.

Risposte & riflessioni

Ecco alcune proposte di soluzione.

Domanda 1a.

figura

Ma ci sono anche altre soluzioni, per esempio:

1<5>3<4<6>2

2<4>1<5<6>3

3<6>2<4<5>1

4<5>1<2<6>3

Domanda 1b.

figura

Domanda 2.

Ci sono almeno tre proposte .

---

Soluzione 1.

Limitandoci all'uso di carta e penna e al fatto che la domanda chiede solo una soluzione (non tutte), ecco un algoritmo applicato all'esempio con 9 numeri.

figura

1) Scrivo nell'ordine i numeri 1, 2, 3, ... nelle caselle seguite dal segno "<"

figura

In questo modo ho scritto tutti i numeri che sono minori di altri numeri. Tutti i numeri che mi restano da scrivere sono sicuramente maggiori di quelli che ho scritto.

Poiché li ho scritti in ordine crescente, sono sicuro che non ci sono inversioni.

2) Scrivo nell'ordine i numeri n, n-1, n-2,... nelle restanti caselle.

figura

In questo modo ho scritto tutti i numeri che sono maggiori dei numeri già scritti. Poiché li ho scritti in ordine decrescente sono sicuro che non ci sono inversioni.

Se i numeri dati non sono 1, 2, 3, ..., n, dapprima li metto in ordine crescente, poi li indicizzo, infine scrivo i vari n(i) nelle caselle i-esime.

Qui sotto c'è l'algoritmo implementato in BASIC.

---
!'Numero dei dati (indici)
DATA 10
!'Sequenza di relazioni
DATA "<",">",">",">",">","<",">",">","<"
!'Inizializzazione variabili
RESTORE
READ n
DIM a(n)
DIM r$(n-1)
LET magg=0
LET mino=0
!'Algoritmo
FOR i=1 TO n-1
   READ a$
   LET r$(i)=a$
   IF a$="<" THEN
      LET mino=mino+1
      LET a(i)=mino
   END IF
   IF a$=">" THEN
      LET magg=magg+1
      LET a(i)=n-magg+1
   END IF
NEXT i
LET a(n)=n-magg
!'Stampa
FOR i=1 TO n-1
   PRINT a(i);r$(i);
NEXT i
PRINT a(n)
END
---

Soluzione 2.

Grazie a Bruno per aver precisato meglio l'algoritmo.

  1. ordino i numeri della lista data;
  2. guardo il segno di disuguaglianza alla destra della prima cella:
    -- se è ">", prendo il massimo della lista e lo scrivo nella prima cella, eliminandolo dalla lista;
    -- se è "<", prendo il minimo della lista e lo scrivo nella prima cella, eliminandolo dalla lista;
  3. ripeto l'operazione per ogni cella successiva, fino a collocare l'ultimo numero nella cella rimasta vuota.

Esempio:

[ ] > [ ] < [ ] < [ ] > [ ] > [ ] > [ ] < [ ] < [ ]

{1,2,3,4,5,6,7,8,9}

[9] > [ ] < [ ] < [ ] > [ ] > [ ] > [ ] < [ ] < [ ]

{1,2,3,4,5,6,7,8}

[9] > [1] < [ ] < [ ] > [ ] > [ ] > [ ] < [ ] < [ ]

{2,3,4,5,6,7,8}

[9] > [1] < [2] < [ ] > [ ] > [ ] > [ ] < [ ] < [ ]

{3,4,5,6,7,8}

[9] > [1] < [2] < [8] > [ ] > [ ] > [ ] < [ ] < [ ]

{3,4,5,6,7}

[9] > [1] < [2] < [8] > [7] > [ ] > [ ] < [ ] < [ ]

{3,4,5,6}

[9] > [1] < [2] < [8] > [7] > [6] > [ ] < [ ] < [ ]

{3,4,5}

[9] > [1] < [2] < [8] > [7] > [6] > [3] < [ ] < [ ]

{4,5}

[9] > [1] < [2] < [8] > [7] > [6] > [3] < [4] < [ ]

{5}

[9] > [1] < [2] < [8] > [7] > [6] > [3] < [4] < [5]

---

Soluzione 3.

Algoritmo proposto da Gnugnu e Franco, da meditare.

Usa come esempio il seguente schema:

figura

Decido di partire da sinistra con l'etichetta "5" (è del tutto indifferente, ma così evito i negativi), aumentando di uno quando transito per un "<" e diminuendo di uno nel caso opposto, ottengo, nell'ordine:

[5,6,5,6,7,6]

Queste etichette rispettano le relazioni d'ordine volute; alcune si ripetono, ma questo indica semplicemente che vi sono, sicuramente, più soluzioni.

Cerco il(i) massimo delle etichette: 7, in quella casella scrivo il maggiore dei numeri proposti 6.

Cerco le caselle marchiate con 6, son tre, in queste scrivo i tre maggiori numeri proposti restanti 3,4,5, non importa in quale ordine.

Cerco le caselle etichettate con 5, sono due, vi scrivo i numeri restanti. Ottenendo ad esempio:

[1,3,2,4,6,5], ma anche

[2,5,1,3,6,4], oppure

[1,4,2,5,6,3]

Se avessi iniziato da destra, poniamo con l'etichetta 2, avrei ottenuto:

[1,2,1,2,3,2] che differiscono dalle etichette trovate prima per una costante (4) e questo si dimostra facilmnte.

NB Le 6⋅2=12 permutazioni generate con questo algoritmo sono, generalmente, lungi dall'esaurire quelle possibili.

---

Pace e bene a tutti.

GfBo

Data creazione: marzo 2020

Ultimo aggiornamento: marzo 2020

xhtml 1.1

Sito Web realizzato da Gianfranco Bo