Indice del forum Olimpo Informatico
I Forum di Zeus News
Leggi la newsletter gratuita - Attiva il Menu compatto
 
 FAQFAQ   CercaCerca   Lista utentiLista utenti   GruppiGruppi   RegistratiRegistrati 
 ProfiloProfilo   Messaggi privatiMessaggi privati   Log inLog in 

    Newsletter RSS Facebook Twitter Contatti Ricerca
Pranzi di Natale
Nuovo argomento   Rispondi    Indice del forum -> Enigmi e giochi matematici
Precedente :: Successivo  
Autore Messaggio
Salmastro
Dio minore
Dio minore


Registrato: 13/12/06 19:36
Messaggi: 883
Residenza: Casalmico

MessaggioInviato: 11 Gen 2010 11:43    Oggetto: Pranzi di Natale Rispondi citando

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
Profilo Invia messaggio privato AIM Yahoo MSN
Scrigno
Semidio
Semidio


Registrato: 26/07/09 04:32
Messaggi: 313

MessaggioInviato: 12 Gen 2010 01:28    Oggetto: Rispondi citando

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
Profilo Invia messaggio privato
Salmastro
Dio minore
Dio minore


Registrato: 13/12/06 19:36
Messaggi: 883
Residenza: Casalmico

MessaggioInviato: 12 Gen 2010 14:11    Oggetto: Rispondi citando

ciao Scrigno!

buono il tuo approccio ed in effetti il tuo metodo è quello che i nostri amici hanno usato la prima volta Wink

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 Rolling Eyes
Top
Profilo Invia messaggio privato AIM Yahoo MSN
Salmastro
Dio minore
Dio minore


Registrato: 13/12/06 19:36
Messaggi: 883
Residenza: Casalmico

MessaggioInviato: 20 Gen 2010 13:06    Oggetto: Rispondi citando

beh, se nessuno interviene, credo che sarà doveroso da parte mia dare la soluzione...

ma aspetto ancora un po'! Wink
Top
Profilo Invia messaggio privato AIM Yahoo MSN
dart
Eroe
Eroe


Registrato: 24/02/09 12:06
Messaggi: 74

MessaggioInviato: 20 Gen 2010 23:50    Oggetto: Rispondi citando

Ah... ero arrivato anch'io alla stessa conclusione!
Se c'è un modo migliore, provo a pensarci... Smile
Top
Profilo Invia messaggio privato
dart
Eroe
Eroe


Registrato: 24/02/09 12:06
Messaggi: 74

MessaggioInviato: 22 Gen 2010 14:54    Oggetto: Rispondi citando

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
Profilo Invia messaggio privato
Salmastro
Dio minore
Dio minore


Registrato: 13/12/06 19:36
Messaggi: 883
Residenza: Casalmico

MessaggioInviato: 22 Gen 2010 15:53    Oggetto: Rispondi citando

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! Very Happy
la tua ultimissima affermazione (che ho grassettato), però, non è completamente corretta Wink
Top
Profilo Invia messaggio privato AIM Yahoo MSN
dart
Eroe
Eroe


Registrato: 24/02/09 12:06
Messaggi: 74

MessaggioInviato: 24 Gen 2010 15:46    Oggetto: Rispondi citando

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
Profilo Invia messaggio privato
Salmastro
Dio minore
Dio minore


Registrato: 13/12/06 19:36
Messaggi: 883
Residenza: Casalmico

MessaggioInviato: 24 Gen 2010 17:50    Oggetto: Rispondi citando

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 Wink
Top
Profilo Invia messaggio privato AIM Yahoo MSN
dart
Eroe
Eroe


Registrato: 24/02/09 12:06
Messaggi: 74

MessaggioInviato: 24 Gen 2010 22:15    Oggetto: Rispondi citando

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
Profilo Invia messaggio privato
Salmastro
Dio minore
Dio minore


Registrato: 13/12/06 19:36
Messaggi: 883
Residenza: Casalmico

MessaggioInviato: 25 Gen 2010 11:12    Oggetto: Rispondi citando

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 Rolling Eyes

ti aspestto! Wink
Top
Profilo Invia messaggio privato AIM Yahoo MSN
dart
Eroe
Eroe


Registrato: 24/02/09 12:06
Messaggi: 74

MessaggioInviato: 25 Gen 2010 15:54    Oggetto: Rispondi citando

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. Sad
Top
Profilo Invia messaggio privato
Salmastro
Dio minore
Dio minore


Registrato: 13/12/06 19:36
Messaggi: 883
Residenza: Casalmico

MessaggioInviato: 25 Gen 2010 23:50    Oggetto: Rispondi citando

ti lascio pensare fino a domani sera: non è difficile! Wink

del caso, posto la mia idea!
Top
Profilo Invia messaggio privato AIM Yahoo MSN
Salmastro
Dio minore
Dio minore


Registrato: 13/12/06 19:36
Messaggi: 883
Residenza: Casalmico

MessaggioInviato: 26 Gen 2010 19:22    Oggetto: Rispondi citando

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 Rolling Eyes
Top
Profilo Invia messaggio privato AIM Yahoo MSN
dart
Eroe
Eroe


Registrato: 24/02/09 12:06
Messaggi: 74

MessaggioInviato: 29 Gen 2010 12:37    Oggetto: Rispondi

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!! Smile
Top
Profilo Invia messaggio privato
Mostra prima i messaggi di:   
Nuovo argomento   Rispondi    Indice del forum -> Enigmi e giochi matematici Tutti i fusi orari sono GMT + 1 ora
Pagina 1 di 1

 
Vai a:  
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