Να προσδιορίσετε τον ελάχιστο ακέραιο k για τον οποίο μπορεί να ισχύει: Σε μία συνάντηση σκακιού με 24 παίκτες, κάθε ζευγάρι παικτών παίζουν μεταξύ τους τουλάχιστον δύο και το πολύ k παιγνίδια.
Στο τέλος της συνάντησης προκύπτει ότι κάθε παίκτης έχει παίξει διαφορετικό αριθμό παιγνιδιών.
16ος ΜΕΣΟΓΕΙΑΚΟΣ ΜΑΘΗΜΑΤΙΚΟΣ ΔΙΑΓΩΝΙΣΜΟΣ 2013
Αυτό το σχόλιο αφαιρέθηκε από τον συντάκτη.
ΑπάντησηΔιαγραφήΑυτό το σχόλιο αφαιρέθηκε από τον συντάκτη.
ΑπάντησηΔιαγραφήΑυτό το σχόλιο αφαιρέθηκε από τον συντάκτη.
ΔιαγραφήΕξαιρετικά ενδιαφέρον πρόβλημα και θα ήταν κρίμα να παραμείνει ασχολίαστο. Επιχειρώ παρακάτω μια, ελπίζω δόκιμη, προσέγγισή του:
ΑπάντησηΔιαγραφήΑν ήταν k=3, τότε ο ελάχιστος δυνατός αριθμός παιχνιδιών ενός παίκτη θα ήταν 2*23=46 και ο μέγιστος 3*23=69. Το διάστημα [46,69] περιέχει 24 ακριβώς ακέραιους, επομένως θα έπρεπε κάθε παίκτης να είχε παίξει, σε αριθμό παιχνιδιών, και έναν διαφορετικό από αυτούς τους ακέραιους. Σε αυτή την περίπτωση, θα υπήρχε παίκτης Α που θα είχε παίξει ακριβώς 2 παιχνίδια με καθέναν από τους υπόλοιπους 23 και ταυτόχρονα θα υπήρχε παίκτης Ω που θα είχε παίξει ακριβώς 3 παιχνίδια με καθέναν από τους υπόλοιπους 23. Δηλαδή, ο Α θα είχε παίξει με τον Ω ακριβώς 2 φορές και ο Ω με τον Α ακριβώς 3 φορές. Αντίφαση, άρα k≠3.
Θα δείξουμε τώρα ότι η περίπτωση k=4 είναι εφικτή.
Ξεκινάμε με 3 παίκτες Α, Β, Γ. Ο Α παίζει με τον Β 2 παιχνίδια και με τον Γ 3 παιχνίδια, ενώ ο Β με τον Γ παίζουν 4 παιχνίδια. Έτσι ο Α παίζει συνολικά 2+3=5 παιχνίδια, ο Β συνολικά 2+4=6 παιχνίδια και ο Γ συνολικά 3+4=7 παιχνίδια.
Προσθέτουμε έναν ακόμα παίκτη Δ που παίζει με καθέναν από τους 3 προηγούμενους από 2 παιχνίδια. Τώρα πλέον έχουμε συνολικά παιχνίδια για κάθε παίκτη:
Α-> 5+2=7, Β-> 6+2=8, Γ->7+2=9, Δ->3*2=6
Προσθέτουμε έναν ακόμα παίκτη Ε που παίζει με καθέναν από τους 4 προηγούμενους από 4 παιχνίδια. Τώρα πλέον έχουμε συνολικά παιχνίδια για κάθε παίκτη:
Α-> 7+4=11, Β-> 8+4=12, Γ->9+4=13, Δ->6+4=10, Ε->4*4=16
Προσθέτουμε έναν ακόμα παίκτη Ζ που παίζει με καθέναν από τους 5 προηγούμενους από 2 παιχνίδια. Τώρα πλέον έχουμε συνολικά παιχνίδια για κάθε παίκτη:
Α-> 11+2=13, Β-> 12+2=14, Γ->13+2=15, Δ->10+2=12, Ε->16+2=18, Ζ->5*2=10
…………………
Η τεχνική συνίσταται στο να προσθέτουμε κάθε φορά και έναν νέο παίκτη, ο οποίος θα παίζει εναλλάξ από 2 ή 4 παιχνίδια με καθέναν από τους προηγούμενους, που έχουν ήδη παίξει μεταξύ τους από 2 έως 4 το πολύ παιχνίδια το ζευγάρι, οπότε έτσι τελικά κανένας δεν παίζει με κανέναν περισσότερα από 4 ή λιγότερα από 2 παιχνίδια και όλοι παίζουν συνολικά διαφορετικό αριθμό παιχνιδιών ο ένας από τον άλλο.
Η πιο πάνω συλλογιστική αποδεικνύεται και επαγωγικά, ως εξής:
Όπως δείξαμε, για 3 παίκτες είναι εφικτό κάθε ζευγάρι να έχουν παίξει μεταξύ τους από 2 έως 4 παιχνίδια και κάθε παίκτης να έχει παίξει διαφορετικό αριθμό παιχνιδιών συνολικά από κάθε άλλον.
Υποθέτουμε τώρα ότι το ζητούμενο είναι εφικτό για ν παίκτες. Μεταξύ των ν παικτών, δεν είναι δυνατό να υπάρχουν ταυτόχρονα δύο παίκτες που ο ένας να έχει παίξει ακριβώς 2 παιχνίδια με καθέναν από τους υπόλοιπους και ο άλλος να έχει παίξει ακριβώς 4 παιχνίδια με καθέναν από τους υπόλοιπους, αφού αυτό θα συνιστούσε αντίφαση. Θα υπάρχει επομένως σίγουρα
ή α)παίκτης που δεν έχει παίξει 2 ακριβώς παιχνίδια με καθέναν από τους ν-1 υπόλοιπους
ή β) παίκτης που δεν έχει παίξει ακριβώς 4 παιχνίδια με καθέναν από τους ν-1 υπόλοιπους.
Αν ισχύει το α), τότε ο παίκτης που έχει παίξει τα λιγότερα παιχνίδια από όλους τους άλλους, θα έχει παίξει περισσότερα από 2*(ν-1)=2ν-2 παιχνίδια συνολικά, αφού θα έχει παίξει 2 τουλάχιστον παιχνίδια με τον καθένα και με κάποιους περισσότερα από 2 παιχνίδια. Στην περίπτωση αυτή, ο (ν+1)στός παίκτης που προστίθεται θα παίξει ακριβώς από 2 παιχνίδια με καθέναν από τους προηγούμενους ν, άρα συνολικά 2ν παιχνίδια, ενώ όλοι οι προηγούμενοι θα προσθέσουν από 2 παιχνίδια έκαστος και έτσι θα παραμείνουν με διαφορετικό αριθμό παιχνιδιών και μεταξύ τους και με τον προστιθέμενο.
Αν ισχύει το β), τότε ο παίκτης που έχει παίξει τα περισσότερα παιχνίδια από όλους τους άλλους, θα έχει παίξει λιγότερα από 4*(ν-1)=4ν-4 παιχνίδια συνολικά. Στην περίπτωση αυτή, ο (ν+1)στός παίκτης που προστίθεται θα παίξει ακριβώς από 4 παιχνίδια με καθέναν από τους προηγούμενους ν, άρα συνολικά 4ν παιχνίδια, ενώ όλοι οι προηγούμενοι θα προσθέσουν από 4παιχνίδια έκαστος και έτσι θα παραμείνουν με διαφορετικό αριθμό παιχνιδιών και μεταξύ τους και με τον προστιθέμενο.
Επομένως, το ζητούμενο είναι εφικτό και για ν+1 παίκτες.
Υπάρχει μια ασάφεια σε ένα σημείο του επαγωγικού επιχειρήματος και γι αυτό το επαναλαμβάνω διορθωμένο:
ΑπάντησηΔιαγραφήΌπως δείξαμε, για 3 παίκτες είναι εφικτό κάθε ζευγάρι να έχουν παίξει μεταξύ τους από 2 έως 4 παιχνίδια και κάθε παίκτης να έχει παίξει διαφορετικό αριθμό παιχνιδιών συνολικά από κάθε άλλον.
Υποθέτουμε τώρα ότι το ζητούμενο είναι εφικτό για ν παίκτες. Μεταξύ των ν παικτών, δεν είναι δυνατό να υπάρχουν ταυτόχρονα δύο παίκτες που α) ο ένας να έχει παίξει ακριβώς 2 παιχνίδια με καθέναν από τους υπόλοιπους και β) ο άλλος να έχει παίξει ακριβώς 4 παιχνίδια με καθέναν από τους υπόλοιπους, αφού αυτό θα συνιστούσε αντίφαση.
Αν δεν ισχύει το α), τότε ο παίκτης που έχει παίξει τα λιγότερα παιχνίδια από όλους τους άλλους, θα έχει παίξει περισσότερα από 2*(ν-1)=2ν-2 παιχνίδια συνολικά, αφού θα έχει παίξει 2 τουλάχιστον παιχνίδια με τον καθένα και με κάποιους από τους άλλους περισσότερα από 2 παιχνίδια με τον καθένα. Στην περίπτωση αυτή, ο (ν+1)στός παίκτης που προστίθεται θα παίξει ακριβώς από 2 παιχνίδια με καθέναν από τους προηγούμενους ν, άρα συνολικά 2ν παιχνίδια, ενώ όλοι οι προηγούμενοι θα προσθέσουν από 2 παιχνίδια έκαστος και έτσι θα παραμείνουν με διαφορετικό αριθμό παιχνιδιών και μεταξύ τους και με τον προστιθέμενο.
Αν δεν ισχύει το β), τότε ο παίκτης που έχει παίξει τα περισσότερα παιχνίδια από όλους τους άλλους, θα έχει παίξει λιγότερα από 4*(ν-1)=4ν-4 παιχνίδια συνολικά. Στην περίπτωση αυτή, ο (ν+1)στός παίκτης που προστίθεται θα παίξει ακριβώς από 4 παιχνίδια με καθέναν από τους προηγούμενους ν, άρα συνολικά 4ν παιχνίδια, ενώ όλοι οι προηγούμενοι θα προσθέσουν από 4 παιχνίδια έκαστος και έτσι θα παραμείνουν με διαφορετικό αριθμό παιχνιδιών και μεταξύ τους και με τον προστιθέμενο.
Επομένως, το ζητούμενο είναι εφικτό και για ν+1 παίκτες.