2. gli ambasciatori e la tavola rotonda

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

2. gli ambasciatori e la tavola rotonda

Messaggioda Livex » 02/06/2013, 15:23

1. Tre divisibilità
propongo un problema che mi piacque moltissimo,spero che non sia troppo conosciuto...

[tex]2n[/tex] ambasciatori sono invitati a un banchetto.Ogni ambasciatore ha al massimo n-1 nemici.Dimostrare che gli ambasciatori possono sedersi intorno ad una tavola rotonda in modo che nessuno sia seduto vicino ad un suo nemico.
Livex
 
Messaggi: 994
Iscritto il: 15/03/2013, 15:33

Re: 2. gli ambasciatori e la tavola rotonda

Messaggioda Drago » 02/06/2013, 16:16

wall98 ha scritto:spero che non sia troppo conosciuto...

E' sull'Engel... xD
Ma non importa, è davvero bello, spero che qualcuno lo provi e lo risolva... :)
Avatar utente
Drago
 
Messaggi: 1056
Iscritto il: 14/03/2013, 15:51

Re: 2. gli ambasciatori e la tavola rotonda

Messaggioda Livex » 06/06/2013, 15:34

ok vah,qui un hint piuttosto (troppo) interessante:
proviamo a mettere gli ambasciatori intorno al tavolo,come possiamo poi ridistribuirli in modo da tornare alle richieste del testo?
Livex
 
Messaggi: 994
Iscritto il: 15/03/2013, 15:33

Re: 2. gli ambasciatori e la tavola rotonda

Messaggioda Livex » 12/06/2013, 9:26

un altro hintino:
proviamo (una volta messi a caso gli ambasciatori) a concentrarsi su un ipotetica coppia di nemici vicini,come possiamo spostare uno di loro in modo che quella coppia,e la nuova che si viene a creare,non creino piu problemi? è possibile ripetere questo procedimento?
Livex
 
Messaggi: 994
Iscritto il: 15/03/2013, 15:33

Re: 2. gli ambasciatori e la tavola rotonda

Messaggioda xXStephXx » 27/06/2013, 18:26

Mi sa che l'avevo visto pure io sull'Engel tempo fa :D Ora se ben ricordo com'era direi che è arrivato il momento di un enotniH :lol:
(ma non vorrei che mi stavo confondendo con uno simile dove c'erano dei vasi che venivano usati per separare la vista degli ambasciatori)
xXStephXx
 
Messaggi: 628
Iscritto il: 23/03/2013, 18:12

Re: 2. gli ambasciatori e la tavola rotonda

Messaggioda Livex » 28/06/2013, 8:34

non ho ben capito che esercizio tu abbia risolto :P
comunque secondo me sarebbe piu risolutivo trasformarlo in tinHone, soprattutto se isacco e Hilbert non vanno d'accordo ma sono amici di tina...
per quanto possiamo ripetere questo ragionamento
Livex
 
Messaggi: 994
Iscritto il: 15/03/2013, 15:33

Re: 2. gli ambasciatori e la tavola rotonda

Messaggioda xXStephXx » 28/06/2013, 19:58

Non intendevo invertire tutto il tavolo in effetti! :D (solo una parte)

Comunque non ho ben capito il tuo hint, intendi scambiare di posto Hilbert con Tina? Se è così come fai ad avere la certezza che Hilbert stia simpatico sia a Nino sia ad Osvlado? (ma probabilmente non intendevi quello)
xXStephXx
 
Messaggi: 628
Iscritto il: 23/03/2013, 18:12

Re: 2. gli ambasciatori e la tavola rotonda

Messaggioda Livex » 28/06/2013, 22:09

spiattelliamo direttamente la soluzione vah...
bhe, forse invertire una part di tavolo potrebbe portare a qualcosa di buono,non so dirtelo con certezza..

no no,intendevo assolutamente quello, se vuoi ti mando la copia di backup dell'engel giusto perche tu veda la soluzione,poi ovviamente provvedero a fartelo cancellare (se mi dai la tua mail ne parliamo per bene), comunque se per qualche ragione Osvaldo e nino sono cattivi mi bastera spostare entrambi,ma chi mi garantisce che posso iterare questo procedimento? e qui entrano in gioco 2n e n-1


PS:per il testo nascosto ti consiglio un bel DDDDDD
Livex
 
Messaggi: 994
Iscritto il: 15/03/2013, 15:33

Re: 2. gli ambasciatori e la tavola rotonda

Messaggioda Livex » 05/07/2013, 14:19

soluzione diversa da quella proposta dall'engel ma ancor piu interessante:
milizia96 ha scritto:Dimostrazione del lemma:
Per "chiudere il cerchio" a partire dalla fila lineare costruita è sufficiente trovare una coppia di ambasciatori vicini in cui il primo di essi è amico del chiudi-fila mentre il secondo di essi è amico dell'apri-fila. Infatti a quel punto basta invertire l'ordine di tutti gli ambasciatori dall'apri-fila fino al primo elemento di una tale coppia, e così facendo nella fila si rispettano ancora i vincoli di amicizia e in più in nuovo apri-fila (che era il primo elemento della coppia) è amico del chiudi-fila. Quindi li posso chiudere in cerchio.

Per vedere che effettivamente esiste una tale coppia, basta osservare che nella fila devono necessariamente comparire tutti gli amici dell'apri-fila e tutti gli amici del chiudi-fila, altrimenti se uno di questi amici fosse rimasto fuori, allora avrei potuto continuare a allungare la fila in costruzione.
Quindi: nella fila ci sono almeno n amici dell'apri-fila, almeno n amici del chiudi-fila, ma tra apri-fila e chiudi-fila ci sono al massimo 2n−2 persone. Insomma, non sto a precisare molto ma per il principio del pigeonhole ho che quella coppia che dicevo esiste veramente.

Benissimo, lemma dimostrato.
Quindi io posso fare così: costruisco questo cerchio a partire da una fila. Se non è rimasto nessuno fuori, allora ho finito. Altrimenti considero uno di quelli rimasti fuori. Egli ha sicuramente almeno un amico che sta nel cerchio, perché come ho detto prima, nel cerchio ci sono più di n persone, quindi fuori sono rimaste meno di n persone, che non possono includere tra loro TUTTI gli amici di un certo ambasciatore. Quindi "riapro" il cerchio facendo in modo che la fila che ne risulti abbia come apri-fila un amico dell'ambasciatore che sto considerando. Quindi amplio la fila finché posso (di sicuro almeno di 1) e richiudo il nuovo cerchio, che sarà sicuramente più grosso di quello di prima. Andando avanti così, il cerchio comprenderà tutti gli ambasciatori in tempo finito.


3. semplice intersezione
Livex
 
Messaggi: 994
Iscritto il: 15/03/2013, 15:33


Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti