Matematicamente.it

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

O non ho capito il problema oppure:

Ed io non ho capito cosa vuoi dire

Piccolo hint:

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.

[/quote]

axpgn ha scritto: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