|
| Precedente :: Successivo |
| Autore |
Messaggio |
Salmastro
Dio minore
Registrato: 13/12/06 20:36
Messaggi: 883
Residenza: Casalmico
|
 Inviato: 11 Gen 2010 12:43 Oggetto: Pranzi di Natale |
 |
|
Come tradizione, anche quest’anno la famiglia Sycamore.Vanderhof si è riunita per i Pranzi di Natale.
Dico “pranzi” perché i nostri bizzarri amici hanno una simpatica usanza, secondo la quale ogni componente della famiglia pretende di sedere a tavola, almeno una volta, con tutti gli altri convenuti.
Sarebbe come minimo razionale che si accomodassero tutti intorno ad un grande tavolo, ma l’estroso patriarca, nonno Martin, non transige: ci sono due tavoli, il primo con M posti, l’altro con N, e lì si devono sistemare!
Fortuna vuole che i Sycamore-Vanderhof siano proprio in numero pari alla somma dei posti disponibili ( N+M), per cui, si chiede nonno Martin (ed io chiedo a voi) quanti “pranzi” bisogna organizzare affinché sia rispettato il loro desiderio che tutti stiano a tavola, almeno una volta, con tutti?
N.B.: stare a tavola con qualcuno non significa stare vicino a quel qualcuno, ma, semplicemente, alla stessa tavola! |
|
| Top |
|
 |
Scrigno
Semidio
Registrato: 26/07/09 05:32
Messaggi: 313
|
| Inviato: 12 Gen 2010 02:28 Oggetto: |
|
|
Se ho ben capito:
| Citazione: | Abbiamo un tavolo con M posti ed un tavolo con N posti ed m + n persone da sedere
Diciamo che le persone ai tavoli sono così disposte:
M1, M2, M3,..., Mm (nel tavolo M)
N1, N2, N3,..., Nn (nel tavolo N)
Poniamo quella sopra come una delle possibili combinazioni e poi togliamo dal tavolo M un membro per cambiarlo con uno del tavolo N; per esempio, M1 con N1. Queste due persone avranno visto, a tavola, tutti tranne loro stesse.
Ora immaginiamo di prendere ancora N1 dal tavolo M e di scambiarlo di posto con N2
A questo punto N2 come N1 avrà visto tutti meno loro due per via dello scambio ma si erano gia incontrati al pranzo precedente.
ora prendiamo N2 sempre dal tavolo M e lo scambiamo con N3 come prima, fra loro si erano gia visti all' inizio mentre gli M li incontra ora meno M1 che aveva incontrato precedentemente al tavolo N
Così facendo avremo che:
StatoIniziale (combinazione 1)
M1 <-> N1 (Combinazione 2)
N1 <-> N2 (Combinazione 3)
N2 <-> N3 (Combinazione 4)
Nn-1 <-> Nn (Combinazione n+1)
Così facendo il valore risulta pari ad N+1 pranzi scegliendo, ovviamente, N come il numero più piccolo tra i due. |
|
|
| Top |
|
|
Salmastro
Dio minore
Registrato: 13/12/06 20:36
Messaggi: 883
Residenza: Casalmico
|
| Inviato: 12 Gen 2010 15:11 Oggetto: |
|
|
ciao Scrigno!
buono il tuo approccio ed in effetti il tuo metodo è quello che i nostri amici hanno usato la prima volta 
ma, accortisi che i "pranzi di natale", così facendo, finivano a metà gennaio, han cercato, poi, di accorciare i tempi e finire, magari, entro l'anno  |
|
| Top |
|
|
Salmastro
Dio minore
Registrato: 13/12/06 20:36
Messaggi: 883
Residenza: Casalmico
|
| Inviato: 20 Gen 2010 14:06 Oggetto: |
|
|
beh, se nessuno interviene, credo che sarà doveroso da parte mia dare la soluzione...
ma aspetto ancora un po'! |
|
| Top |
|
|
dart
Eroe
Registrato: 24/02/09 13:06
Messaggi: 74
|
| Inviato: 21 Gen 2010 00:50 Oggetto: |
|
|
Ah... ero arrivato anch'io alla stessa conclusione!
Se c'è un modo migliore, provo a pensarci...  |
|
| Top |
|
|
dart
Eroe
Registrato: 24/02/09 13:06
Messaggi: 74
|
| Inviato: 22 Gen 2010 15:54 Oggetto: |
|
|
Eheh... hai ragione.
| Citazione: | Nel caso in cui N è pari (con N<=M), sono sufficienti 3 soli pranzi:
Il primo pranzo, con N ad un tavolo ed M nell'altro.
Il secondo, con il gruppo N1 (composto da N/2 persone) che si sposta dal tavolo "N" al tavolo "M" e viceversa.
L'ultimo, con il gruppo N2 che si scambia di posto con il gruppo N1.
Con N dispari, credo sia necessario un ulteriore pranzo... |
|
|
| Top |
|
|
Salmastro
Dio minore
Registrato: 13/12/06 20:36
Messaggi: 883
Residenza: Casalmico
|
| Inviato: 22 Gen 2010 16:53 Oggetto: |
|
|
| dart ha scritto: | Eheh... hai ragione.
| Citazione: | Nel caso in cui N è pari (con N<=M), sono sufficienti 3 soli pranzi:
Il primo pranzo, con N ad un tavolo ed M nell'altro.
Il secondo, con il gruppo N1 (composto da N/2 persone) che si sposta dal tavolo "N" al tavolo "M" e viceversa.
L'ultimo, con il gruppo N2 che si scambia di posto con il gruppo N1.
Con N dispari, credo sia necessario un ulteriore pranzo... |
|
ottima idea!, bravo! 
la tua ultimissima affermazione (che ho grassettato), però, non è completamente corretta |
|
| Top |
|
|
dart
Eroe
Registrato: 24/02/09 13:06
Messaggi: 74
|
| Inviato: 24 Gen 2010 16:46 Oggetto: |
|
|
Dopo attente riflessioni...
| Citazione: | Con M >= 2N sono sufficienti 3 pranzi...
Ma con M compreso tra N e 2N, non riesco a scendere sotto ai 4. |
|
|
| Top |
|
|
Salmastro
Dio minore
Registrato: 13/12/06 20:36
Messaggi: 883
Residenza: Casalmico
|
| Inviato: 24 Gen 2010 18:50 Oggetto: |
|
|
| dart ha scritto: | Dopo attente riflessioni...
| Citazione: | Con M >= 2N sono sufficienti 3 pranzi...
Ma con M compreso tra N e 2N, non riesco a scendere sotto ai 4. |
|
se raggruppi i vari casi in un unico post mi (ci) aiuti a commentare |
|
| Top |
|
|
dart
Eroe
Registrato: 24/02/09 13:06
Messaggi: 74
|
| Inviato: 24 Gen 2010 23:15 Oggetto: |
|
|
| Citazione: | Ci sono 2 tavoli, con N e M posti, con N <= M.
N pari.
sono sufficienti 3 soli pranzi:
il primo pranzo, con N ad un tavolo ed M nell'altro;
il secondo, con il gruppo N1 (composto da N/2 persone) che si sposta dal tavolo "N" al tavolo "M" e viceversa;
l'ultimo, con il gruppo N2 che si scambia di posto con il gruppo N1.
N dispari.
Se M >= 2N sono sufficienti sempre 3 pranzi.
Se M è compreso tra N e 2N, sono necessari 4 pranzi. |
|
|
| Top |
|
|
Salmastro
Dio minore
Registrato: 13/12/06 20:36
Messaggi: 883
Residenza: Casalmico
|
| Inviato: 25 Gen 2010 12:12 Oggetto: |
|
|
| dart ha scritto: | | Citazione: | Ci sono 2 tavoli, con N e M posti, con N <= M.
N pari.
sono sufficienti 3 soli pranzi:
il primo pranzo, con N ad un tavolo ed M nell'altro;
il secondo, con il gruppo N1 (composto da N/2 persone) che si sposta dal tavolo "N" al tavolo "M" e viceversa;
l'ultimo, con il gruppo N2 che si scambia di posto con il gruppo N1.
N dispari.
Se M >= 2N sono sufficienti sempre 3 pranzi.
Se M è compreso tra N e 2N, sono necessari 4 pranzi. |
|
attenzione: il "grassettato" non è sempre vero
ti aspestto! |
|
| Top |
|
|
dart
Eroe
Registrato: 24/02/09 13:06
Messaggi: 74
|
| Inviato: 25 Gen 2010 16:54 Oggetto: |
|
|
Con "Se M è compreso tra N e 2N" intendevo "2N escluso".
Se c'è qualche caso nel quale M è compreso tra N e 2N-1 e sono sufficienti 3 soli pranzi... non l'ho trovato...
Mi arrendo.  |
|
| Top |
|
|
Salmastro
Dio minore
Registrato: 13/12/06 20:36
Messaggi: 883
Residenza: Casalmico
|
| Inviato: 26 Gen 2010 00:50 Oggetto: |
|
|
ti lascio pensare fino a domani sera: non è difficile!
del caso, posto la mia idea! |
|
| Top |
|
|
Salmastro
Dio minore
Registrato: 13/12/06 20:36
Messaggi: 883
Residenza: Casalmico
|
| Inviato: 26 Gen 2010 20:22 Oggetto: |
|
|
| dart ha scritto: | | Se c'è qualche caso nel quale M è compreso tra N e 2N-1 e sono sufficienti 3 soli pranzi... non l'ho trovato... |
Beh, se per esempio:
| Citazione: | | M=8 e N=5, divido il tavolo M in due gruppi, 4+4, ed quello N in altri due gruppi: 4+1. Il single rimane sempre nel tavolo N, mentre i tre gruppi da 4 “ruotano”. |
In generale, invece, io la vedo così:
| Citazione: | escluso a priori che si possa risolvere con un solo pranzo, altrettanto evidente è che 2 non bastano, proviamo con 3, partendo con un numero piccolo di commensali.
Con 3 commensali, i soli tavoli utili sono M=2 e N=1
Si riesce a far mangiare tutti con tutti semplicemente lasciando da solo, nei tre pranzi uno dei commensali: cioè 1° (A,B), ( C ); 2° (A,C), (B); 3° (B,C), (A).
Aumentiamo di uno i commensali: portiamoli a 4: A,B,C,D.
Due sono le possibilità per i tavoli: 3+1 e 2+2, vale a dire [(A,B,C)(D)] e [(A,B)(C,D)]
Anche stavolta bastano solo 3 pranzi: nel caso 3+1 A rimane fisso nel tavolo M, gli altre 3 ruotano in modo tale che uno alla volta mangi da solo nel tavolo N.
Nel caso 2+2, A, che rimane sempre al tavolo M, di volta in volta pranza con uno degli altri 3.
Verificato quanto sopra è quasi spontaneo trattare i due generici tavoli M e N come occupati non da 4 commensali, ma da 4 gruppi di commensali: se riusciamo a riprodurre quanto fatto sopra, risolviamo il problema! Ed, infatti, quasi, sempre ci si riesce:
M pari, N pari
i) Se M >2N, allora si ha la disposizione [(A,B,C)(D)], così realizzata [(X,N,N)(N)], dove X=M-2N
ii) Se M<2N, [(A,B)(C,D)] = [(X, N/2) (N/2, N/2)], con X = M – N/2
in sostanza il gruppo individuato da X commensali è quello che non ruota!
esempi:
i) per M=8 e N=2, si ha [(4,2,2) (2)]
ii) per M=8 e N=6, si ha [(5,3) (3,3)]
N.B.: se M=2N, allora X=0 e si rientra nel caso dei “3 commensali”
M pari, N dispari
i) Se M >2N, allora si ha la disposizione [(A,B,C)(D)], così realizzata [(X,N,N)(N)], dove X=M-2N
ii) Se M<2N, [(A,B)(C,D)] = [(M/2, M/2) (X, M/2)], con X = N – M/2 (anche stavolta X non ruota)
esempi:
i) per M=8 e N=3, si ha [(2,3,3) (3)]
ii) per M=8 e N=5, si ha [(4,4) (1,4)]
M dispari, N pari
i) Se M >2N, allora si ha la disposizione [(A,B,C)(D)], così realizzata [(X,N,N)(N)], dove X=M-2N
ii) Se M<2N, [(A,B)(C,D)] = [(X, N/2) (N/2, N/2)], con X = M – N/2 (e X non ruota!)
esempi:
i) per M=9 e N=4, si ha [(1,4,4) (4)]
ii) per M=9 e N=6, si ha [(6,3) (3,3)]
M dispari, N dispari
i) Se M >2N, allora si ha la disposizione [(A,B,C)(D)], così realizzata [(X,N,N)(N)], dove X=M-2N
ii) Se M<2N, ahimè, non si può con soli 3 pranzi!!!
esempi:
i) per M=7 e N=3, si ha [(1,3,3) (3)]
ii) per M=7 e N=5….non si può….e vediamo perché…
Si siano divisi i commensali in quattro distinti gruppi: A e B che mangiano al tavolo M(<2N) e C e D nel tavolo N. Nel secondo pranzo B va nel tavolo N e C nel tavolo M (B = C), vale a dire:
1° pranzo, M = A + B; N = C + D
2° pranzo, M = A + C; N = B + C
Nel terzo pranzo dovremmo far mangiare insieme C e B (nonché A e D, nell’altro tavolo), ma B + C è un numero pari (così come A + D) e non c’è un tavolo con un numero pari di posti per poterlo accogliere!
Per inciso, nell’altro caso M>2N, ci riusciamo giacché “mettendo da parte” un numero di commensali pari a M-2N otteniamo tre gruppi, formati da N/2 persone, che riusciamo a ruotare per restare nei tre pranzi. |
spero di non aver dimenticato nulla e, soprattutto, di non avervi annoiato |
|
| Top |
|
|
dart
Eroe
Registrato: 24/02/09 13:06
Messaggi: 74
|
| Inviato: 29 Gen 2010 13:37 Oggetto: |
 |
|
In effetti ci sarei dovuto arrivare, era lo stesso ragionamento... tieni fermi alcuni elementi (di N o di M) e dividi gli altri in 3 gruppi che girano.
Solo che io cercavo di risolvere con 3 e 5 persone, o 5 e 9... e non ci riuscivo!! |
|
| Top |
|
|
|
|
Non puoi inserire nuovi argomenti
Non puoi rispondere a nessun argomento
Non puoi modificare i tuoi messaggi
Non puoi cancellare i tuoi messaggi
Non puoi votare nei sondaggi
|
|
FAQ
Cerca
Lista utenti
Gruppi
Registrati
Profilo
Messaggi privati
Log in
