IMC selection 2026, Problem 2
Δίνεται ένας πίνακας με στοιχεία μη αρνητικούς πραγματικούς αριθμούς για τον οποίο το στοιχείο στην πρώτη γραμμή και δεύτερη στήλη του πίνακα είναι ίσο με μηδέν. Να δείξετε ότι υπάρχουν μη κενά και ξένα υποσύνολα του με ένωση τέτοια ώστε για κάθε και κάθε να έχουμε .
Original from the official PDF

This transcription was compared symbol by symbol with the original, but not yet by a person.
Work for at least 45 minutes before opening the solution.
Official solution
Κατασκευάζουμε ένα κατευθυνόμενο γράφημα με κορυφές τα και κατευθυνόμενες ακμές (θα το γράφουμε και ως ) για κάθε διατεταγμένο ζεύγος δεικτών τέτοιο ώστε .
Ισχυρισμός: Δεν υπάρχει μονοπάτι στο κατευθυνόμενο γράφημα.
Γιατι μπορουμε να εχουμε οτι στο μονοπατι δεν επαναλαμβανεται καποιος δεικτης, αρα και , που είναι άτοπο από την υπόθεση .
Θέτουμε λοιπόν
Transcribed from the official solutions, page 2. This transcription has not been checked a second time; if in doubt, look at the original.
Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.
How did it go?
Moves you mark come back sooner in triage.