Precedente :: Successivo |
Autore |
Messaggio |
Salmastro Dio minore
Registrato: 13/12/06 19:36 Messaggi: 883 Residenza: Casalmico
|
Inviato: 25 Gen 2010 11: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 12:06 Messaggi: 74
|
Inviato: 25 Gen 2010 15: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 19:36 Messaggi: 883 Residenza: Casalmico
|
Inviato: 25 Gen 2010 23: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 19:36 Messaggi: 883 Residenza: Casalmico
|
Inviato: 26 Gen 2010 19: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 12:06 Messaggi: 74
|
Inviato: 29 Gen 2010 12: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
|
|