socrates έγραψε:
Πρόβλημα 4
Σε έναν μακρινό πλανήτη, οι κάτοικοι χρησιμοποιούν για τις συναλλαγές τους νομίσματα με μία άσπρη και μία μαύρη πλευρά. Σε κάθε πλευρά των νομισμάτων είναι γραμμένος ένας θετικός ακέραιος που δεν υπερβαίνει το

(οι δύο πλευρές δεν έχουν απαραίτητα γραμμένο τον ίδιο αριθμό).
Δύο νομίσματα λέγονται
όμοια αν στην άσπρη πλευρά τους έχουν γραμμένο τον ίδιο αριθμό και στη μαύρη πλευρά τους έχουν γραμμένο τον ίδιο αριθμό. Δύο νομίσματα λέγονται
ζευγαρωτά αν έχουν γραμμένο τον ίδιο αριθμό σε μία τουλάχιστον πλευρά του ίδιου χρώματος.
Ένας κάτοικος αυτού του πλανήτη έχει

νομίσματα. Ανάμεσά τους δεν υπάρχουν όμοια νομίσματα.
Να δείξετε ότι υπάρχει νόμισμα που είναι ζευγαρωτό με τουλάχιστον άλλα

νομίσματα.
Ισοδύναμα θέλουμε να δείξουμε ότι αν τοποθετήσουμε

πιόνια σε μια

σκακιέρα, το πολύ ένα σε κάθε τετραγωνάκι, τότε υπάρχει ένα πιόνι ώστε στην σειρά του και στην στήλη του υπάρχουν τουλάχιστον άλλα

πιόνια.
Θα δείξω ότι το πιο πάνω συμπέρασμα ισχύει ακόμη και αν τοποθετήσουμε

πιόνια.
Έστω μια τοποθέτηση πιονιών μεγίστου πλήθους ώστε κάθε πιόνι να έχει στην σειρά του και στήλη του το πολύ άλλα

πιόνια.
Έστω επιπλέον ότι οι σειρές έχουν

πιόνια αντίστοιχα. Αν

τότε μπορώ να βρω μια στήλη στην οποία υπάρχει πιόνι στην

σειρά αλλά όχι στην

. Αν μετακινήσω το πιόνι αυτό από την

σειρά στην

, τότε εξακολουθεί να ισχύει ότι κάθε πιόνι έχει στην σειρά του και στήλη του το πολύ άλλα

πιόνια.
Κάνοντας συνεχώς τέτοιες μετακινήσεις μπορώ να υποθέσει ότι υπάρχει

ώστε όλες οι σειρές έχουν είτε

είτε

πιόνια. Κάνοντας το ίδιο και για τις στήλες (οι αντίστοιχες μετακινήσεις δεν τροποποιούν το πλήθος των πιονιών της κάθε σειράς) μπορώ να υποθέσω ότι υπάρχει

ώστε όλες οι στήλες έχουν είτε

είτε

πιόνια.
Έστω τώρα ότι υπάρχει σειρά με τουλάχιστον

πιόνια. Παίρνω τώρα ένα πιόνι σε αυτήν την σειρά. Στην σειρά του έχει

άλλα πιόνια. Στην στήλη του πρέπει να έχει το πολύ άλλα

πιόνια. Άρα

. Δηλαδή κάθε στήλη έχει το πολύ

πιόνια. Αυτό είναι άτοπο αφού κάθε σειρά έχει τουλάχιστον

πιόνια.
Πρέπει λοιπόν

. Αν

τότε έχουμε το πολύ

πιόνια και τελειώσαμε. Ας υποθέσουμε λοιπόν ότι

. Έστω ότι έχουμε

σειρές με

πιόνια και

με

πιόνια. Άρα θα έχουμε και

στήλες με

πιόνια και

με

πιόνια.
Παίρνω ένα πιόνι που βρίσκεται σε μια σειρά με

πιόνια. Στην στήλη του πρέπει να υπάρχουν

πιόνια αφού αν υπάρχουν

θα καταλήξουμε σε άτοπο όπως προηγουμένως. Άρα όλα τα πιόνια των

σειρών με

πιόνια, βρίσκονται στις

στήλες με τα

πιόνια. Συνολικά σε αυτές τις σειρές/στήλες έχουμε

πιόνια. Επίσης υπάρχουν το πολύ

πιόνια.
Άρα

. Τότε

οπότε

. Συνολικά λοιπόν έχουμε

πιόνια.
Άρα αν τοποθετήσουμε

πιόνια θα έχουμε ένα πιόνι του οποίου στην σειρά και στήλη θα υπάρχουν τουλάχιστον άλλα

.
[Δεν είναι δύσκολο να κάνουμε κατασκευή με

πιόνια.]