Il campione di un intero torneo deve battere il campione di un possibile torneo tra gli altri giocatori?

Question

Ho un elenco di "giocatori" di un "torneo". Uno due adiacente I giocatori possono "competere", il che provoca il perdente espulso dal torneo. Vincere non è transitivo. È noto il vincitore di una determinata competizione tra due giocatori, ma l'ordine delle competizioni non lo è. Supponiamo di avere qualche torneo della forma $ p_1, p_2, p_3, ..., p_n $ E lo so $ p_1 $ può vincere l'intero torneo (a seconda dell'ordine delle competizioni). Posso mostrarlo $ p_1 $ Deve battere un possibile vincitore di un torneo solo $ p_2, p_3, ..., p_n $?

Inizialmente ci sono arrivato mentre provavo la correttezza di un algoritmo per determinare l'elenco dei possibili vincitori di un torneo generale, ma questo specifico sottoproblema mi sta dando problemi.

Per iniziare un tentativo di una soluzione, lo offro nel caso contrario, $ p_1 $ dovere solo competere contro e battere una sequenza di "perdenti" (giocatori che non possono vincere il torneo $ p_2, ..., p_n $ Non importa l'ordine giocato), senza che i vincitori perdano $ p_1 $. Ciò implica che ad un certo punto un perdente deve sconfiggere un vincitore. Questo potrebbe essere impossibile? Non posso provarlo e non so se sia anche vero.