Putnam 2012/B3
Συντονιστής: Demetres
- Demetres
- Γενικός Συντονιστής
- Δημοσιεύσεις: 8989
- Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
- Τοποθεσία: Λεμεσός/Πύλα
- Επικοινωνία:
Putnam 2012/B3
Σε ένα τουρνουά λαμβάνουν μέρος ομάδες. Το τουρνουά διαρκεί μέρες και κάθε μέρα κάθε ομάδα παίζει ένα αγώνα εναντίον μίας άλλης ομάδας με κάθε ένα από τους αγώνες να λήγει με ένα νικητή. Το τουρνουά διαρκεί μέρες και κατά την διάρκεια του τουρνουά κάθε ομάδα έπαιξε με κάθε άλλη ομάδα από μία φορά.
Μπορούμε σίγουρα να επιλέξουμε για κάθε μέρα μία νικήτρια ομάδα ώστε καμία ομάδα να μην επιλεχθεί περισσότερες από μία φορά;
Μπορούμε σίγουρα να επιλέξουμε για κάθε μέρα μία νικήτρια ομάδα ώστε καμία ομάδα να μην επιλεχθεί περισσότερες από μία φορά;
Λέξεις Κλειδιά:
Re: Putnam 2012/B3
Ναι, μπορούμε.
Έστω το σύνολο των νικητών της -οστής ημέρας. Για οποιεσδήποτε ημέρες, δεν είναι δυνατόν να υπάρχουν ομάδες που να έχασαν και στις ημέρες. Πράγματι, για οποιεσδήποτε ομάδες, κάθε μία θα έχει παίξει με τουλάχιστον άλλη μία μέσα σε ημέρες και μία από τις δύο θα έχει κερδίσει.
Άρα, για οποιεσδήποτε ημέρες θα υπάρχουν τουλάχιστον νικητές. Έπεται ότι η οικογένεια πληροί τις προϋποθέσεις του Hall's Marriage Theorem και, κατά συνέπεια, μπορούμε να επιλέξουμε για κάθε μέρα έναν νικητή έτσι ώστε κανένας να μην επιλεγεί πάνω από μία φορά.
Έστω το σύνολο των νικητών της -οστής ημέρας. Για οποιεσδήποτε ημέρες, δεν είναι δυνατόν να υπάρχουν ομάδες που να έχασαν και στις ημέρες. Πράγματι, για οποιεσδήποτε ομάδες, κάθε μία θα έχει παίξει με τουλάχιστον άλλη μία μέσα σε ημέρες και μία από τις δύο θα έχει κερδίσει.
Άρα, για οποιεσδήποτε ημέρες θα υπάρχουν τουλάχιστον νικητές. Έπεται ότι η οικογένεια πληροί τις προϋποθέσεις του Hall's Marriage Theorem και, κατά συνέπεια, μπορούμε να επιλέξουμε για κάθε μέρα έναν νικητή έτσι ώστε κανένας να μην επιλεγεί πάνω από μία φορά.
Δημήτρης Σκουτέρης
Τα μαθηματικά είναι η μοναδική επιστήμη που θα μπορούσε κανείς να εξακολουθήσει να ασκεί αν κάποτε ξυπνούσε και το σύμπαν δεν υπήρχε πλέον.
Τα μαθηματικά είναι η μοναδική επιστήμη που θα μπορούσε κανείς να εξακολουθήσει να ασκεί αν κάποτε ξυπνούσε και το σύμπαν δεν υπήρχε πλέον.
Μέλη σε σύνδεση
Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 2 επισκέπτες