Il problema di Futurama

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Il professor Farnsworth ha inventato una macchina che scambia le menti e i corpi di due persone. Dopo diversi scambi ci si ritrova nella seguente situazione
- Nel corpo di Fry c'è la mente del Dott. Zoidberg.
- Nel corpo di Leela c'è la mente del Conrad.
- Nel corpo di Bender c'è la mente del Prof. Farnsworth.
- Nel corpo del Prof. Farnsworth c'è la mente di Leela.
- Nel corpo di Conrad c'è la mente di Wong.
- Nel corpo del Dott. Zoidberg c'è la mente di Fry.
- Nel corpo di Wong c'è la mente di un secchio d'acqua.
- Nel secchio d'acqua c'è la mente del Robot Emperor.
- Nel corpo di Emperor c'è la mente di Bender.

Il problema è che quando due corpi hanno scambiato la loro mente (indipendentemente dalla mente che vi era dentro) non è più possibile per quei due corpi scambiarsi la mente (indipendentemente dalla mente che c'è ora dentro al corpo) e loro non si ricordano più quale quali corpi si sono già scambiati due menti.

Qual è il numero minimo di giocatori di Basket che devono trovare (il cui corpo non ha cambiato mente con nessuno) per far in modo che tutte le menti tornano nel loro proprio corpo? E come fanno a tornare tutti nel proprio corpo, compresi i giocatori di Basket?

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Nessuno?

[axpgn]

lee [con] <> con [won] --> lee [won] <> con [CON]
lee [won] <> won [acq] --> lee [acq] <> won [WON]
lee [acq] <> acq [emp] --> lee [emp] <> acq [ACQ]
lee [emp] <> emp [ben] --> lee [ben] <> emp [EMP]
lee [ben] <> ben [far] --> lee [far] <> ben [BEN]
lee [far] <> far [lee] --> lee [LEE] <> far [FAR]

fry [zoi] <> zoi [fry] --> fry [FRY] <> zoi [ZOI]

E non dirmi che l'ultimo scambio non si può fare perché non sappiamo come si è arrivati a quella situazione e potrebbe darsi che non si siano scambiati direttamente la mente ma attraverso altri scambi (d'altronde non se lo ricordano nemmeno loro, che poi cosa significa quel "loro" ? )

IMHO, le condizioni non sono chiarissime ...

Cordialmente, Alex

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

edit:

E non dirmi che l'ultimo scambio non si può fare perché non sappiamo come si è arrivati a quella situazione e potrebbe darsi che non si siano scambiati direttamente la mente ma attraverso altri scambi (d'altronde non se lo ricordano nemmeno loro, che poi cosa significa quel "loro" ? )

Invece è proprio così.

D'altronde la domanda è: quanti giocatori di Basket devono trovare, tu non ne hai usato nemmeno uno.

Le condizioni sono chiare. Tu "axpgn" ti ritrovi davanti a questa situazione qui di menti e corpi, non hai idea di come si sono fatti degli scambi prima e ti chiedono: "Aiutaci axpgn, non sappiamo come tornare nei rispettivi corpi. Abbiamo un'intera squadra di Basket che può aiutarci (e che non si sono ancora scambiati la mente con nessuno), come facciamo a tornare nelle nostre menti?"
Tu gli chiedi: "Come siete arrivati a questa situazione"
E ti rispondono
"Non lo sappiamo..."

Come gli aiuti?

Loro significa che tutti i personaggi presenti non hanno nessuna idea degli scambi che hanno fatto perché ne hanno fatti tanti e hanno perso il conto semplicemente.

[axpgn]

IMHO, non sei molto chiaro

"3m0o":Invece è proprio così.

"Invece è proprio così" cosa? Quello che dico io o quello che dici tu?

"3m0o":D'altronde la domanda è: quanti giocatori di Basket devono trovare, tu non ne hai usato nemmeno uno.

E dove sta scritto che devo usarne obbligatoriamente almeno uno?
E poi cosa c'entrano i giocatori di Basket? Vuoi mettere un limite superiore? Ma non sarebbe chiaro quale: 5, 10 o 12?

"3m0o":Loro significa che ...

"Loro" chi? Le menti o i corpi?

IMHO, non sei molto chiaro

Cordialmente, Alex

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Uhhh madò...

"Invece è proprio così" cosa? Quello che dico io o quello che dici tu?

Non è accettabile la tua soluzione perché non sai che scambi hanno fatto prima.
"invece è proprio così" = ti dico che non è valido.

E dove sta scritto che devo usarne obbligatoriamente almeno uno?
E poi cosa c'entrano i giocatori di Basket? Vuoi mettere un limite superiore? Ma non sarebbe chiaro quale: 5, 10 o 12?

Non c'è scritto, ma mi sembra abbastanza chiaro che non sapendo gli scambi effettuati in precedenza ne devi usare almeno uno perché ogni scambio senza giocatori di Basket potrebbe essere illegale. Ad esempio tu dici il primo scambio lo faccio
Lee [con] <-> con [won]

Potrebbe essere valido perché la mente di Conrad potrebbe essere finito nel corpo di Leela attraverso uno scambio intermedio con qualcun altro. Ma potrebbe essere illegale perché potrebbe essere che il corpo di Leela si sia scambiata direttamente con il corpo di Conrad e poi è il corpo di Conrad che ha cambiato la mente di Leela con qualcuno d'altro. Non lo sai.

"Loro" chi? Le menti o i corpi?

...

[axpgn]

Comunque ...

fry [zoi] <> b1 [B1] --> fry [b1] <> b1 [zoi]
zoi [fry] <> b2 [B2] --> zoi [b2] <> b2 [fry]
zoi [b2] <> b1 [zoi] --> zoi [ZOI] <> b1 [b2]
fry [b1] <> b2 [fry] --> fry [FRY] <> b2 [b1]
b1 [b2] <> b2 [b1] --> b1 [B1] <> b2 [B2]

Cordialmente, Alex

[axpgn]

E smettila con gli "EDIT" che già ci capisco poco, se mi cambi le carte in tavola diventa un casino!

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

"axpgn":Comunque ...

fry [zoi] <> b1 [B1] --> fry [b1] <> b1 [zoi]
zoi [fry] <> b2 [B2] --> zoi [b2] <> b2 [fry]
zoi [b2] <> b1 [zoi] --> zoi [ZOI] <> b1 [b2]
fry [b1] <> b2 [fry] --> fry [FRY] <> b2 [b1]
b1 [b2] <> b2 [b1] --> b1 [B1] <> b2 [B2]

Cordialmente, Alex

No! Ma penso tu abbia capito come utilizzare i giocatori di Basket. Devi fare questa cosa fin dall'inizio, senza scambiare corpi tra loro perché ogni singolo scambio che fai prima (nel primo spoiler) non sai se è una mossa che puoi fare.

Edit

"axpgn":E smettila con gli "EDIT" che già ci capisco poco, se mi cambi le carte in tavola diventa un casino!

Va bene

[axpgn]

Va beh, che dovevo usare quel giochetto l'avevo capito ma va bene anche come dico io

Comunque ne dovrebbero bastare due ... Lee cede il suo ad un giocatore di basket che si fa tutto il "giro" e rimane alla fine con Lee; a questo punto arriva il secondo giocatore che mette a posto il Dottore da Fry;
quindi Lee [b1], Fry [b2], b1 [Lee] e b2 [Fry] e fanno lo scambio come ho detto nell'ultimo (o penultimo) post.
Va bene?

Cordialmente, Alex

[axpgn]

Ricapitolo ...

Gli scambi sono questi:

LEE B1
B1 CON
B1 WON
B1 ACQ
B1 EMP
B1 BEN
B1 FAR
B1 FRY
B1 ZOY
B2 LEE
LEE FRY
B2 B1
B2 FRY

Due giocatori di basket utilizzati.

Ok?

Cordialmente, Alex

[axpgn]

... mmmm ... non va bene neppure questo ...

Sono arrivato alla conclusione che occorrano due giocatori per ogni "ciclo" ed in questo caso ci sono due "cicli" quindi quattro giocatori; non so se si può fare di meglio ...

Cordialmente, Alex

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

"axpgn":Ricapitolo ...

Gli scambi sono questi:

LEE B1
B1 CON
B1 WON
B1 ACQ
B1 EMP
B1 BEN
B1 FAR
B1 FRY
B1 ZOY
B2 LEE
LEE FRY
B2 B1
B2 FRY

Due giocatori di basket utilizzati.

Ok?

Cordialmente, Alex

Non riesco troppo a capire chi stai scambiando con chi, perché non capisco quelli scritti sono le menti che scambi o i corpi
Comunque credo che arrivi ad un problema perché i due giocatori di Basket non puoi più scambiarli e farli tornare nei propri copri.

"axpgn":... mmmm ... non va bene neppure questo ...

Sono arrivato alla conclusione che occorrano due giocatori per ogni "ciclo" ed in questo caso ci sono due "cicli" quindi quattro giocatori; non so se si può fare di meglio ...

Cordialmente, Alex

Bastano 2 giocatori di Basket, indipendentemente dal numero di cicli che si ha

[axpgn]

@3m0o

"3m0o":Comunque credo che arrivi ad un problema perché i due giocatori di Basket non puoi più scambiarli e farli tornare nei propri copri.

Non è quello il problema, gli scambi funzionano perfettamente e tutto torna a posto, l'inghippo di cui mi sono accorto solo poi e lo scambio FRY - LEE che è "vietato" dalle condizioni del problema (sono "nomi di corpi").
Con due soli giocatori non ci sono ancora riuscito ma penso che lascerò perdere ...

Cordialmente, Alex

[Bokonon]

Io dico 3 giocatori.
Fondamentalmente è sufficiente un pivot (che è il termine appropriato ) per scambiare in modo ordinato anche $n$ menti e poi ci si trova in una situazione del tipo $A_b$ e $B_a$ dove il pedice è la mente e i corpi A e B non si possono scambiare. Per risolvere la situazione servono altri due giocatori

[axpgn]

Forse ci sono arrivato ...

Es. $A_b, B_c, C_d, D_a, F_g, G_f$
Il primo giocatore $X_x$ prende da $A$ che diventa $A_x$, dà $b$ a $B$, $c$ a $C$, $d$ a $D$ e rimane $X_a$ che dà a $F$ quindi $F_a$ e $X_g$
Interviene il secondo giocatore che prende $f$ da $G$, la dà a $F$, si prende la $a$ che dà ad $A$ (primo giro chiuso), $X$ dà $g$ a $G$ (secondo giro chiuso) e rimangono $X_y$ e $Y_x$ che si scambiano fra loro.

Cordialmente, Alex

[axpgn]

E quindi ricapitolando (si spera per l'ultima volta )

$L_c <=> X_x\ \ \ -> \ \ \ L_x : X_c$
$C_w <=> X_c\ \ \ ->\ \ \ C_c : X_w\ \ \ ->\ \ \ [Cc]$
$W_a <=> X_w\ \ \ ->\ \ \ W_w : X_a\ \ \ ->\ \ \ [Ww]$
$A_e <=> X_a\ \ \ -> \ \ \ A_a : X_e\ \ \ ->\ \ \ [Aa]$
$E_b <=> X_e\ \ \ -> \ \ \ E_e : X_b\ \ \ ->\ \ \ [Ee]$
$B_p <=> X_b\ \ \ -> \ \ \ B_b : X_p\ \ \ ->\ \ \ [Bb]$
$P_l <=> X_p\ \ \ -> \ \ \ P_p : X_l\ \ \ ->\ \ \ [Pp]$
$Z_f <=> X_l\ \ \ -> \ \ \ Z_l : X_f$
$F_z <=> Y_y\ \ \ -> \ \ \ F_y : Y_z$
$Z_l <=> Y_z\ \ \ -> \ \ \ Z_z : Y_l\ \ \ ->\ \ \ [Zz]$
$L_x <=> Y_l\ \ \ -> \ \ \ L_l : Y_x\ \ \ ->\ \ \ [Ll]$
$F_y <=> X_f\ \ \ -> \ \ \ F_f : X_y\ \ \ ->\ \ \ [Ff]$
$Y_x <=> X_y\ \ \ -> \ \ \ Y_y : X_x\ \ \ ->\ \ \ [Xx, Yy]$

Cordialmente, Alex

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

@axpgn

Penso che funzioni come hai fatto te! L'unica differenza che vedo tra come ho fatto io e come hai fatto te e che tu passi al ciclo successivo io chiudo un ciclo direttamente senza mai scambiare i due.
Io ho fatto così:
Il primo ciclo
\( A_b, B_c, C_d, D_e ,E_f ,F_g, G_a \)
il secondo è
\( H_i, I_h \).

I due giocatori di basket sono \(X_x , Y_y \).

\( (X_x,A_b) \mapsto (X_b,A_x) \)
\( (X_b,B_c) \mapsto (X_c,B_b) \)
\( \vdots \)
\( (X_e,E_f) \mapsto (X_f,E_e) \)
\( (X_f,F_g) \mapsto (X_g,F_f) \)
\( ( Y_y, G_a) \mapsto (Y_a, G_y) \)
\( (Y_a, A_x ) \mapsto (Y_x, A_a )\)
\( ( X_g, G_y ) \mapsto ( X_y, G_y) \).

Il primo ciclo è tutte le menti sono nel proprio corpo. E \( X,Y \) non si sono scambiati mai quindi possiamo risolvere ogni ciclo successivo in questo modo e alla fine sistemati tutti i cicli scambiamo eventualmente \(X_y \) con \( Y_x \).

Per completezza l'ultimo ciclo lo facciamo così
\( ( X_y, H_i ) \mapsto ( X_i , H_y ) \)
\( ( Y_x, I_h) \mapsto (Y_h, I_x) \)
\( ( X_i, I_x ) \mapsto ( X_x , I_i ) \)
\( ( Y_h, H_x) \mapsto (Y_y, H_h) \)

In questo caso, siccome abbiamo un numero pari di cicli non è necessario scambiare \( X \) e \(Y \) perché terminati i cicli si ritroveranno automaticamente nelle proprie menti. Se avessimo avuto un numero dispari di cicli allora avremmo dovuto scambiarli.

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

@bokonon

No, non sono 3.
E va bene anche scambi, siccome sono trasposizioni.