Il costo minimo

Il forum di Base5, dove è possibile postare problemi, quiz, indovinelli, rompicapo, enigmi e quant'altro riguardi la matematica ricreativa e oltre.

Moderatori: Gianfranco, Bruno

franco
Livello 8
Livello 8
Messaggi: 1222
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Il costo minimo

Messaggio da franco »

Cento carte numerate da 1 a 100 sono allineate in ordine crescente.
L'obiettivo è scambiarne due per volta sino ad averle allineate in ordine inverso.
Le uniche mosse ammesse sono:
- Scambiare due carte adiacenti (costo = 1€)
- Scambiare due carte fra le quali stanno esattamente k=3 carte (gratis)
Qual è il costo minimo?

P.S. se volete, ripetete l'esercizio per k=4

www.diophante.fr
E5903
***

Cent cartes numérotées de 1 à 100 sont alignées dans cet ordre sur une même rangée.
La permutation de deux cartes adjacentes coute un euro tandis que la permutation de deux cartes avec exactement k cartes placées entre elles est gratuite.
Déterminer le coût minimal du classement des cartes dans l’ordre inverse de 100 à 1 avec a) k = 3 et b) k = 4.
Franco

ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician

giobimbo
Livello 5
Livello 5
Messaggi: 269
Iscritto il: sab nov 19, 2005 5:14 pm
Località: Biella

Re: Il costo minimo

Messaggio da giobimbo »

Io ci riesco spendendo 150 euro; se nessuno riesce a far meglio spiegherò come ci sono arrivato. Col metodo che ho usato il costo C del riordino è dato dalla formula

C=(n*k!)/(k+1)

dove n è il numero delle carte; quindi per k=4 C=10*100/5=200 euro.

delfo52
Livello 9
Livello 9
Messaggi: 1526
Iscritto il: mer mag 25, 2005 4:19 pm
Località: bologna

Re: Il costo minimo

Messaggio da delfo52 »

io parto piano piano.
per far arrivare il num. 1 in fondo alla fila, non posso sperare di cavarmela gratis. I salti gratuiti portano 1 ai posti 4n+1 Cioè si arriva al massimo al 97esimo posto, e poi ...tocca pagare. Con uno scambio all'indietro (non conta a quale punto del viaggio, il num 1 si posiziona in una casella 4n, da cui arriva gratis in 100esima posizione. costo= 1 euro

il numero 2 deve arrivare al posto 99esimo. Arriva gratis a 98, poi con euro, si piazza . Un euro
al numero 3 basta fare un passo indietro, per poi arrivare gratis al 98esimo posto. Un euro
il quattro arriva gratis al 96esimo posto, e con un euro si ferma al 97. Un euro
Sembra che un euro sia la spesa massima. Forse c'entra qualcosa il "modulo4" che non so che cosa è.
Il giochino si può fare sia spostandosi verso l'alto che verso il basso.
Non escludo che qualche pedina si venga a trovare al posto giusto anche "a gratis"

SE&O
Enrico

giobimbo
Livello 5
Livello 5
Messaggi: 269
Iscritto il: sab nov 19, 2005 5:14 pm
Località: Biella

Re: Il costo minimo

Messaggio da giobimbo »

Bisogna dire che Delfo52 è un maestro del pensiero laterale, col suo metodo si abbassa notevolmente il costo del riordino. Però bisogna mandare una carta che sta in posizione dispari in una posizione pari e viceversa (facendo 4 passi per volta), quindi per i numeri da 1 a 96 bisogna pagare 96 euro (96 scambi di due carte adiacenti).
Facendo una prova con 12 carte risulta che dopo gli scambi fatti sfruttando l’opzione gratis le carte risulteranno:

97 98 99 100 96 95 94… e via decrescendo fino ad arrivare a 1. Per riordinare le prime 4 carte occorrono (4-1)!=6 scambi che portano il costo C ad un totale di 102 euro.

delfo52
Livello 9
Livello 9
Messaggi: 1526
Iscritto il: mer mag 25, 2005 4:19 pm
Località: bologna

Re: Il costo minimo

Messaggio da delfo52 »

ulteriore sasso in piccionaia. giobimbo parla di posizioni pari e dispari. ma ogni carta è sia l'una che l'altra cosa. a seconda da dove iniziamo a contare. Non so se la cosa ha influenza sul risultato
Enrico

giobimbo
Livello 5
Livello 5
Messaggi: 269
Iscritto il: sab nov 19, 2005 5:14 pm
Località: Biella

Re: Il costo minimo

Messaggio da giobimbo »

Dobbiamo mandare la carta 1 (posizione 1) al posto della carta 100 (posizione 100), quindi a (100-1)=99 passi di distanza.
Dobbiamo mandare la carta 2 (posizione 2) al posto della carta 99 (posizione 99), quindi a (99-2)=97 passi di distanza.
Dobbiamo mandare la carta 3 (posizione 3) al posto della carta 98 (posizione 98), quindi a (98-3)=95 passi di distanza.
E così via.

Le distanze da percorrere sono sempre dispari ma usando l’opzione “gratis” i passi che facciamo sono sempre 4, numero pari, allora bisogna fare uno scambio, pagando 1 euro, per arrivare alla posizione desiderata.
Spero di aver calmato le acque… dello stagno. E i piccioni.. :wink:

franco
Livello 8
Livello 8
Messaggi: 1222
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Re: Il costo minimo

Messaggio da franco »

Andando avanti a sistemare nel posto desiderato le carte da 1 in avanti sembra effettivamente che ci sia da pagare 1€ per ciascuna.
Alla fine però ci sono alcune carte che finiscono al loro posto "in automatico".

Io ho provato a fare una simulazione con 18 carte e riesco a invertire l'ordine pagando 15€.
costomin.PNG
costomin.PNG (23.9 KiB) Visto 611 volte
Per estensione, si potrebbe ipotizzare che con 100 carte si spendano 97€.

C'è però da capire se non ci sia qualche strategia migliore ...
Franco

ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician

franco
Livello 8
Livello 8
Messaggi: 1222
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Re: Il costo minimo

Messaggio da franco »

... giusto il tempo di provarci e la strategia migliora ...

Se faccio lo scambio a pagamento all'inizio del ciclo di posizionamento delle carte (anzichè alla fine come avevo fatto in precedenza), si trovano un sacco di opportunità di risparmio:
costomin2.PNG
costomin2.PNG (25.03 KiB) Visto 610 volte
Franco

ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1281
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Il costo minimo

Messaggio da Gianfranco »

Se dispongo le carte come illustrato nella figura (00=100)...
costi.png
costi.png (20.66 KiB) Visto 586 volte
... osservo che:

a) ogni scambio di due colonne affiancate costa 0 €;
perciò, passare dalla situazione A alla situazione B costa 0 €.

b) ogni scambio di due righe sovrapposte costa 25 €;
perciò, passare dalla situazione B alla C costa come un ordinamento BUBBLE-SORT di 4 elementi nella peggiore delle ipotesi, cioè 150 €.

Come disse Giobimbo!
Pace e bene a tutti.
Gianfranco

franco
Livello 8
Livello 8
Messaggi: 1222
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Re: Il costo minimo

Messaggio da franco »

Gianfranco ha scritto:
lun mar 08, 2021 10:45 pm
Se dispongo le carte come illustrato nella figura (00=100)...
...
perciò, passare dalla situazione B alla C costa come un ordinamento BUBBLE-SORT di 4 elementi nella peggiore delle ipotesi, cioè 150 €.
Non so ...
Ho riprovato a fare gli scambi "a mano" con 16 carte e riesco a invertire la sequenza spendendo solo 12 € (e non escludo si possa far meglio).
costomin3.PNG
costomin3.PNG (69.56 KiB) Visto 572 volte
Non sono in grado di spiegare bene perchè ma mi sembra che, escluso l'ultimo pezzo della sequenza, per piazzare ogni carta al posto giusto al massimo si spenda 1 € e parecchie vadano a posto gratis ...
Franco

ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician

franco
Livello 8
Livello 8
Messaggi: 1222
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Re: Il costo minimo

Messaggio da franco »

... si può far meglio: 8€ per 16 carte:
costomin4.PNG
costomin4.PNG (69.29 KiB) Visto 568 volte
Considerando che con 18 carte avevo trovato il modo si spendere 9€ mi viene la tentazione di generalizzare a N/2 ...
Franco

ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1281
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Il costo minimo

Messaggio da Gianfranco »

franco ha scritto:
mar mar 09, 2021 10:02 am
Considerando che con 18 carte avevo trovato il modo si spendere 9€ mi viene la tentazione di generalizzare a N/2 ...
Credo di sì.
Scusate se continuo a usare la mia rappresentazione, adattata alle idee di Franco.
Con 20 carte.
franco1.png
franco1.png (28.45 KiB) Visto 550 volte
1) Per prima cosa, bisogna scambiare la riga B con la C, e questo costa 1/4 del numero delle carte.
2) Poi bisogna scambiare la riga A con la riga D, e questo costa ancora 1/4 del numero delle carte, PERCHE'...
ogni scambio come quelli indicati con le frecce verdi si può ridurre al costo di 1 €, come quello del tipo 5-4, facendo opportuni slittamenti sulle righe, che sono gratis.

franco2.png
franco2.png (6.93 KiB) Visto 550 volte
3) Una volta messe a posto le righe, mettiamo a posto le colonne, con opportuni slittamenti gratuiti.
4) Per arrivare alla disposizione finale.
franco3.png
franco3.png (5.75 KiB) Visto 550 volte
Con questo metodo, il costo totale è 1/2 del numero di carte è generalizzabile a qualunque numero di carte multiplo di 4.

Salvo errori e omissioni.
Pace e bene a tutti.
Gianfranco

franco
Livello 8
Livello 8
Messaggi: 1222
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Re: Il costo minimo

Messaggio da franco »

Ottimo Gianfranco,
La spiegazione con la tua rappresentazione adesso mi è molto chiara.
Se si conoscesse sufficientemente il Francese sarebbe carino mandare la soluzione al sito diophante.fr da cui ho preso il problema.

Volendo, c'è anche la seconda domanda che prevedeva uno scambio gratis per due carte intervallate da altre 4.
Immagino che con il tuo tipo di rappresentazione si possa facilmente arrivare ad una soluzione per qualsiasi numero di carte multiplo di 5.

Così senza ragionarci troppo, ho idea che si debbano spendere 80€ :wink:
Franco

ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician

franco
Livello 8
Livello 8
Messaggi: 1222
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Re: Il costo minimo

Messaggio da franco »

Facendo un'ulteriore generalizzazione sul problema originale e utilizzando la rappresentazione di Gianfranco, si può calcolare il costo minimo per un numero N di carte qualsiasi:
costomin5.PNG
costomin5.PNG (22.96 KiB) Visto 534 volte
Franco

ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician

Bruno
Livello 9
Livello 9
Messaggi: 1599
Iscritto il: lun nov 21, 2005 6:07 pm
Località: Bologna

Re: Il costo minimo

Messaggio da Bruno »

In questi giorni non riesco a trattenermi con voi e sto leggendo al volo.


franco ha scritto:
mer mar 10, 2021 7:54 am
Se si conoscesse sufficientemente il Francese sarebbe carino mandare la soluzione al sito diophante.fr da cui ho preso il problema.

Perdonatemi :roll: rispetto al fatto che il testo del problema faccia riferimento a un allineamento con ben precise operazioni da compiere, è indifferente secondo voi l'impacchettamento brillantissimo di Gianfranco?
(Bruno)

...........................
Invisibile un vento
l'ha apena sfioragia
sospension d'un momento;
e la bola iridessente gera 'ndagia.
{Biagio Marin}
................................................................
Meglio soluzioni sbagliate che risposte esatte.
{Rudi Mathematici}

Rispondi