olymmath

CGMO 2019 Problem 8

    For a tournament with 88 vertices, if from any vertex it is impossible to follow a route to return to itself, we call the graph a good graph. Otherwise, we call it a bad graph. Prove that (1)(1) there exists a tournament with 88 vertices such that after changing the orientation of any at most 77 edges of the tournament, the graph is always abad graph; (2)(2) for any tournament with 88 vertices, one can change the orientation of at most 88 edges of the tournament to get a good graph. (A tournament is a complete graph with directed edges.)

    Dataset text AI-MO AoPS. Quoted with source.

    Solutions

    No solution is on olymmath yet. Official and human solutions come first when they arrive. AI solutions come after them, with a label.

    Add a solution

    Similar problems

    These problems have the most words in common with this statement.

    Locator cn-gmo/2019/p8 · Tag 1B598YVRQM · Edit this page on GitHub · Keys: j next, k previous