Εκατό αγόρια συμμετείχαν σε ένα τουρνουά τένις στο οποίο κάθε παίκτης έπαιξε με κάθε άλλον παίκτη ακριβώς μία φορά και δεν υπήρξαν ισοπαλίες.
Αποδείξτε ότι μετά το τουρνουά, είναι δυνατόν τα αγόρια να παραταχθούν στη σειρά έτσι ώστε κάθε αγόρι να νικήσει το αγόρι που στέκεται ακριβώς πίσω του.
Μπορεί να διατυπωθεί μία λύση με χρήση μαθηματικής επαγωγής, αλλά δεν με ικανοποιεί ιδιαίτερα. Καμμιά ιδέα για "ευθεία" λύση;
ΑπάντησηΔιαγραφήΣτράτο, ελπίζω οι παρακάτω ιδέες να απαντούν κάπως στις προσδοκίες σου☺:
ΑπάντησηΔιαγραφήΑς υποθέσουμε ότι κάθε παίχτης Χ έχει σε μια λίστα Λ(Χ) τους παίκτες που είτε κέρδισε ο Χ είτε κέρδισαν όσοι έχασαν από τον Χ. Η Λ(Χ) περιέχει έναν τουλάχιστον παίχτη που κέρδισε ο Χ, αλλιώς είναι κενή.
Έστω Α παίκτης που κέρδισε τις περισσότερες νίκες στο τουρνουά. Η λίστα Λ(Α) περιέχει και τους 99 άλλους παίκτες, πλην του Α, γιατί αν έλειπε κάποιος, έστω ο Ω, τότε η αντίστοιχη λίστα Λ(Ω) θα περιείχε τόσο τον Α (αφού ο Α δεν θα είχε κερδίσει τον Ω, άρα ο Ω θα είχε κερδίσει τον Α) , όσο και όλα τα μέλη της Λ(Α) (αφού τον Ω δεν θα είχε κερδίσει κανένας από όσους κέρδισε ο Α). Σε τέτοια περίπτωση όμως η Λ(Ω) θα περιείχε περισσότερα μέλη από όσα η Λ(Α), αντίφαση.
Εφαρμόζοντας την ίδια συλλογιστική στα 99 μέλη της λίστας Λ(Α), για τους μεταξύ αυτών αγώνες, συμπεραίνουμε ότι ανάμεσά τους υπάρχει παίχτης Β που η λίστα του Λ(Β) περιέχει και τους 98 άλλους παίκτες. Εφαρμόζουμε διαδοχικά τα ίδια για τους 98 της λίστας Λ(Β), τους 97 της λίστας Λ(Γ) κ.ο.κ.
Έτσι, καταλήγουμε τελικά ότι υπάρχει διάταξη των 100 παικτών, όπου ο Α κέρδισε τον Β, ο Β κέρδισε τον Γ, ..., ο Ψ κέρδισε τον Ω.
Αυτό το σχόλιο αφαιρέθηκε από τον συντάκτη.
ΔιαγραφήΉ πιο απλά:
ΔιαγραφήΒάζουμε μπροστά τον παίκτη Α με τις περισσότερες νίκες στο τουρνουά (Αν είναι περισσότεροι από έναν, βάζουμε έναν από αυτούς). Πίσω από τον Α βάζουμε, από το σύνολο των παιχτών που νίκησε ο Α, τον παίκτη Β με τις αμέσως λιγότερες νίκες. Πίσω από τον Β βάζουμε, από το σύνολο των παιχτών που νίκησε ο Β, τον παίκτη Γ με τις αμέσως λιγότερες νίκες κ.ο.κ.
Ή διάταξη ΑΒΓ..ΨΩ είναι μια διάταξη των 100 παιχτών όπως τη θέλουμε.
Διευκρίνιση:..με ΙΣΕΣ Ή, ΑΝ ΔΕΝ ΥΠΑΡΧΟΥΝ ΙΣΕΣ, τις αμέσως λιγότερες νίκες..
ΑπάντησηΔιαγραφήΤο πρόβλημα, με όρους θεωρίας γράφων, διατυπώνεται ως εξής: κάθε τουρνουά έχει τουλάχιστον ένα χαμιλτονιανό μονοπάτι.
ΑπάντησηΔιαγραφήΉ επαγωγική απόδειξη της πρότασης (υποθέτω αυτήν εννοούσε και ο Στράτος) είναι απλή:
Για 1 ή δύο παίκτες προφανώς ισχύει.
Υποθέτουμε ότι ισχύει για ν παίκτες (ν>2), π.χ. με μια διάταξη π(1)-π(2)-π(3)-...-π(ν), και δείχνουμε ότι θα ισχύει αναγκαστικά και για ν+1 παίκτες:
-Αν ο παίχτης π(ν+1) νίκησε τον π(1), τον βάζουμε μπροστά από τον π(1).
- Αν ο π(ν+1) ηττήθηκε από τον π(ν), τον βάζουμε πίσω από τον π(ν).
- Αν δεν συνέβη τίποτε από τα παραπάνω, προχωρώντας στη διάταξη των ν παιχτών, διαδοχικά από τον π(1) μέχρι τον π(ν), είναι βέβαιο ότι σε κάποιο σημείο της διάταξης βρίσκεται παίκτης π(ι) που νίκησε τον π(ν+1), ενώ ο π(ι+1) ηττήθηκε από τον π(ν+1). Ο π(ν+1) μπορεί έτσι να τοποθετηθεί ανάμεσα στον π(ι) και τον π(ι+1).
Σε κάθε περίπτωση, η πρόταση ισχύει για ν+1 παίκτες.
Ακριβώς αυτή την απόδειξη είχα κατά νου Θανάση. Γενικώς όμως η επαγωγή (όπως και η εις άτοπον απαγωγή), παρ'ότι είναι μαθηματικά απόλυτα αποδεκτές, μου αφήνουν μία "ανοστη" γεύση, μου αρέσουν περισσότερο οι "κατά μέτωπο" αποδείξεις (εφ'όσον βέβαια μπορούν να διατυπωθούν)
ΑπάντησηΔιαγραφή