Spie

[axpgn]

A Port Moresby ci sono $16$ agenti segreti.
Ogni agente sorveglia uno o più altri agenti ma non ci sono due agenti che si sorvegliano l'uno con l'altro.
Inoltre, presi $10$ agenti qualsiasi, essi possono essere ordinati in modo che uno ne osservi un secondo, il secondo ne osservi un terzo, ecc, e l'ultimo osserva il primo.

Mostrare che $11$ agenti possono essere ordinati allo stesso modo.


Cordialmente, Alex

[3m0o]

O non ho capito il problema oppure:

Testo nascosto, fai click qui per vederlo

Due cicli disgiunti. Uno di lunghezza 11 e l'altro di lunghezza 5.

[axpgn]

Ed io non ho capito cosa vuoi dire

Piccolo hint:

Testo nascosto, fai click qui per vederlo

Prova a determinare quanti altri agenti (min/max) un agente può sorvegliare e viceversa da quanti è osservato

[3m0o]

Testo nascosto, fai click qui per vederlo

Ciclio di lunghezza 11: 1 osserva 2, 2 osserva 3, 3 osserva 4, ..., 10 osserva 11, 11 osserva 10
Ciclio di lunghezza 5: 12 osserva 13, 13 osserva 14, 14 osserva 15, 15 osserva 16, 16 osserva 12

Ciascun agente osserva uno o più altri, inoltre non ce ne sono due che si osservano a vicenda. Inoltre anche se non richiesto ciascuno è osservato da qualcun'altro.

[axpgn]

Non so dirti sui due piedi se esista o se possa esistere un ciclo da 5 ma ... non mi interessa ... concentrati su quello da 10 e dimostra che ne esista sempre anche uno da 11 (date le condizioni).

Forse non è chiaro che, per ipotesi, esiste sempre un ciclo da 10 qualsiasi sottoinsieme di 10 agenti estrai dai 16.

[3m0o]

[/quote]

Non so dirti sui due piedi se esista o se possa esistere un ciclo da 5 ma ... non mi interessa ... concentrati su quello da 10 e dimostra che ne esista sempre anche uno da 11 (date le condizioni).

Forse non è chiaro che, per ipotesi, esiste sempre un ciclo da 10 qualsiasi sottoinsieme di 10 agenti estrai dai 16.

Okay quindi sono disposti in modo tale che esiste un ciclio da 10 e devo dimostrare che esiste un ciclo da 11. Ora è chiaro