Il costo minimo
Moderatori: Gianfranco, Bruno
Questo forum è una sezione del PORTALE DI BASE CINQUE
Il costo minimo
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.
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
ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician
Re: Il costo minimo
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.
C=(n*k!)/(k+1)
dove n è il numero delle carte; quindi per k=4 C=10*100/5=200 euro.
Re: Il costo minimo
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
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
Re: Il costo minimo
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.
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.
Re: Il costo minimo
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
Re: Il costo minimo
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..
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..
Re: Il costo minimo
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€. Per estensione, si potrebbe ipotizzare che con 100 carte si spendano 97€.
C'è però da capire se non ci sia qualche strategia migliore ...
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€. 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
ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician
Re: Il costo minimo
... 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:
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:
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
ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician
-
- Supervisore del sito
- Messaggi: 1729
- Iscritto il: ven mag 20, 2005 9:51 pm
- Località: Sestri Levante
- Contatta:
Re: Il costo minimo
Se dispongo le carte come illustrato nella figura (00=100)...
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!
... 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
Gianfranco
Re: Il costo minimo
Non so ...Gianfranco ha scritto: ↑lun mar 08, 2021 10:45 pmSe 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 €.
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). 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
ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician
Re: Il costo minimo
... si può far meglio: 8€ per 16 carte:
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
ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician
-
- Supervisore del sito
- Messaggi: 1729
- Iscritto il: ven mag 20, 2005 9:51 pm
- Località: Sestri Levante
- Contatta:
Re: Il costo minimo
Credo di sì.
Scusate se continuo a usare la mia rappresentazione, adattata alle idee di Franco.
Con 20 carte. 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.
3) Una volta messe a posto le righe, mettiamo a posto le colonne, con opportuni slittamenti gratuiti.
4) Per arrivare alla disposizione finale.
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
Gianfranco
Re: Il costo minimo
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€
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€
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
ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician
Re: Il costo minimo
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:
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
ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician
Re: Il costo minimo
In questi giorni non riesco a trattenermi con voi e sto leggendo al volo.
Perdonatemi 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?
Perdonatemi 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}
...........................
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}