Il gioco delle sedie

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.

Il gioco delle sedie

Messaggioda Gizeta » 15/12/2013, 9:29

Tutte le sedie in una classe sono sistemate in un quadrato [tex]n[/tex] x [tex]n[/tex] con [tex]n[/tex] colonne ed [tex]n[/tex] righe (quindi una sedia per quadratino), e ogni sedia è occupata da uno studente. La maestra decide di riarrangiare gli studenti secondo le seguenti due regole:

[tex]\cdot[/tex] Ogni studente deve spostarsi su una nuova sedia.

[tex]\cdot[/tex] Uno studente può muoversi solo su una sedia adiacente nella sua stessa riga o colonna. In altre parole, ogni studente può muoversi solamente di una sedia in orizzontale o verticale.

(N.B. Due studenti posti vicini possono scambiarsi i posti tra di loro.)

Mostrare che questa procedura può essere compiuta se e solo se [tex]n[/tex] è pari.
Gizeta
 
Messaggi: 826
Iscritto il: 27/11/2013, 17:16

Re: Il gioco delle sedie

Messaggioda Archimede » 15/12/2013, 9:39

Non mi è chiara una cosa: uno stesso studente può sposarsi più di una volta?
Archimede
 
Messaggi: 313
Iscritto il: 27/11/2013, 14:33

Re: Il gioco delle sedie

Messaggioda Gizeta » 15/12/2013, 9:47

No, da quello che ho capito.
Gizeta
 
Messaggi: 826
Iscritto il: 27/11/2013, 17:16

Re: Il gioco delle sedie

Messaggioda Archimede » 15/12/2013, 9:57

Allora scambiare di posto due studenti corrisponde a ricoprire il quadrato con pezzi di grandezza [tex]2[/tex] x [tex]1[/tex].
Osserviamo quindi che un quadrato con lato pari è composto da un numero pari di caselle e quindi è ricopribile da pezzi di tale grandezza, mentre un quadrato di lato dispari possiede un numero dispari di caselle e quindi non può essere ricoperto da pezzi di tale grandezza..
Può andare?
Archimede
 
Messaggi: 313
Iscritto il: 27/11/2013, 14:33

Re: Il gioco delle sedie

Messaggioda Drago » 15/12/2013, 9:59

Non è detto che gli studenti si scambino a coppie; potrebbero, che so, scalare tutti sulla stessa fila... :)
Avatar utente
Drago
 
Messaggi: 1056
Iscritto il: 14/03/2013, 15:51

Re: Il gioco delle sedie

Messaggioda Gizeta » 15/12/2013, 10:46

Però quadrato da ricoprire con pezzi [tex]2[/tex] x [tex]1[/tex] dovrebbe far venire in mente una cosa :)
Gizeta
 
Messaggi: 826
Iscritto il: 27/11/2013, 17:16

Re: Il gioco delle sedie

Messaggioda xXStephXx » 15/12/2013, 14:38

Bello mi ha incuriosito
di preciso cosche
fa venire in mente
quella tassellazione?
xXStephXx
 
Messaggi: 628
Iscritto il: 23/03/2013, 18:12

Re: Il gioco delle sedie

Messaggioda b8dc4 » 15/12/2013, 18:27

La tesi è vera anche
nel caso in cui gli studenti
possono spostarsi
soltanto in diagonale?
b8dc4
 
Messaggi: 80
Iscritto il: 08/05/2013, 15:33

Re: Il gioco delle sedie

Messaggioda Archimede » 15/12/2013, 18:41

Se é un vostro modo per dire che c'entrano le colorazioni lo avevo intuito da un po e l'unica cosa che mi é venuta in mente é questa:
Colorando tutto come una scacchiera, se questa ha un numero dispari di caselle, ho che il numero di caselle bianche ( o nere) é pari a 1 più il numero delle caselle nere ( o bianche). Quindi nel momento in cui ognuno di loro cambia posto, cambia anche colore, ma ciò é impossibile perché uno di loro non potrà...
Ma non penso che questa valga come dimostrazione
Archimede
 
Messaggi: 313
Iscritto il: 27/11/2013, 14:33

Re: Il gioco delle sedie

Messaggioda b8dc4 » 15/12/2013, 18:45

Certo che vale come dimostrazione! Molta gente considera che le dimostrazione che usano la colorazione non siano valide, ma in realtà è legittimissimo usarle. Ti consiglio di guardare "problem solving strategies" di Arthur Engel, se non sbaglio il secondo capitolo è sulle colorazioni.
Ultima modifica di b8dc4 il 15/12/2013, 18:49, modificato 1 volta in totale.
b8dc4
 
Messaggi: 80
Iscritto il: 08/05/2013, 15:33

Prossimo

Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Google [Bot] e 1 ospite