Τετάρτη, 7 Δεκεμβρίου 2016

Ριζικές ανακατατάξεις

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

4 σχόλια:

  1. Εφόσον η βαθμολογική κατάταξη των παιχτών είναι αυστηρή (δεν υπάρχουν ισοβαθμίες), η βαθμολογική διαφορά μεταξύ δύο διαδοχικών στην κατάταξη παιχτών, είτε στο τέλος του α' γύρου είτε στο τέλος του τουρνουά, θα πρέπει να είναι τουλάχιστον μισός βαθμός.
    Ας υποθέσουμε ΧΒΓ ότι ο τελευταίος της κατάταξης του α' γύρου, ξεκινάει τον β' γύρο παίζοντας κατά σειρά με τον δεύτερο από το τέλος μέχρι τον πρώτο από την αρχή. Για να καταλήξει πρώτος στην τελική κατάταξη, θα πρέπει σε κάθε παιχνίδι να ανεβαίνει στη βαθμολογική κατάταξη και μία ακριβώς θέση (δεν μπορεί να ανέβει δύο θέσεις, αφού τότε θα έπρεπε να κερδίζει σε ένα παιχνίδι περισσότερους από 1 βαθμούς). Για να συμβεί όμως αυτό, πρέπει η βαθμολογική διαφορά μεταξύ δύο οποιωνδήποτε διαδοχικών στην κατάταξη παιχτών στον α' γύρο να είναι ακριβώς μισός βαθμός και ο τελευταίος του α' γύρου να κερδίσει όλα τα παιχνίδια του β' γύρου.
    Με ανάλογη συλλογιστική, για να καταλήξει ο προτελευταίος του α' γύρου δεύτερος στην τελική βαθμολογία, πρέπει στον β' γύρο να κερδίσει όλους τους πάνω από αυτόν στη βαθμολογία του α' γύρου, το ίδιο και ο τρίτος από το τέλος του α' γύρου κ.ο.κ.
    Επομένως, αν έχουμε ν παίχτες συνολικά, για να μπορεί να υπάρξει στο τέλος αντιστροφή της βαθμολογικής κατάταξης του α' γύρου, θα πρέπει στον β' γύρο ο τελευταίος του α' γύρου να κάνει ν-1 νίκες, ο προτελευταίος ν-2 νίκες και 1 ήττα, .... και ο πρώτος 0 νίκες και ν-1 ήττες.

    Στην περίπτωση 9 παιχτών, σε κάθε γύρο γίνονται 9*8/2=36 παιχνίδια και μοιράζονται 36 βαθμοί. Αν ο τελευταίος πήρε στον α' γύρο τ βαθμούς, τότε σύμφωνα με τα παραπάνω, οι προηγούμενοί του στη βαθμολογία του α' γύρου θα έπρεπε να έχουν τ+0,5, τ+1, τ+1,5, ..., τ+4 βαθμούς αντιστοίχως και συνολικά 9τ+18=36 => τ=2. Επομένως οι βαθμοί του α' γύρου θα ήταν
    κατά φθίνουσα σειρά 6-5,5-5-4,5-4-3,5-3-2,5-2, ενώ οι  βαθμοί του β' γύρου θα ήταν 0-1-2-3-4-5-6-7-8 και οι συνολικοί τελικοί βαθμοί 6-6,5-7-7,5-8-8,5-9-9,5-10.
    Η βαθμολογία του α' γύρου θα μπορούσε να προκύψει ως εξής:
    Ο πρώτος της κατάταξης φέρνει ισοπαλίες με τους 4 επόμενούς του και κερδίζει τους 4 τελευταίους (6 βαθμοί).
    Ο δεύτερος της κατάταξης φέρνει ισοπαλίες με τον πρώτο και τους 4 επόμενούς του και κερδίζει τους 3 τελευταίους (5,5 βαθμοί).
    Ο τρίτος της κατάταξης φέρνει ισοπαλίες με τον πρώτο, το δεύτερο και τους 4 επόμενούς του και κερδίζει τους 2 τελευταίους (5 βαθμοί).
    Ο τέταρτος της κατάταξης φέρνει ισοπαλίες με τον πρώτο, το δεύτερο, τον τρίτο και τους 4 επόμενούς του και κερδίζει τον 1 τελευταίο (4,5 βαθμοί).
    Ο πέμπτος της κατάταξης φέρνει ισοπαλίες με όλους (4 βαθμοί)
    Οι παίχτες από τον έκτο μέχρι τον ένατο φέρνουν ισοπαλίες στα μεταξύ τους παιχνίδια και ισοπαλίες ή ήττες, όπως πιο πάνω, στα παιχνίδια με τους 5 προηγούμενους στην κατάταξη (3,5, 3, 2,5 και 2 βαθμοί αντιστοίχως).

    Στην περίπτωση 10 παιχτών, σε κάθε γύρο γίνονται 10*9/2=45 παιχνίδια και μοιράζονται 45 βαθμοί. Αν ο τελευταίος πήρε στον α' γύρο τ βαθμούς, τότε οι προηγούμενοί του στη βαθμολογία του α' γύρου θα έπρεπε να έχουν τ+0,5, τ+1, τ+1,5, ..., τ+4,5 βαθμούς αντιστοίχως και συνολικά 10τ+22,5=45 => τ=2,25. Αλλά οι βαθμοί που μπορεί να έχει οποιοσδήποτε παίχτης σε κάθε φάση του τουρνουά είναι υποχρεωτικά της μορφής 0,5*ακέραιος, πράγμα που ο 2,25 δεν είναι. Επομένως για 10 παίχτες, το ζητούμενο δεν είναι εφικτό.

    ΑπάντησηΔιαγραφή
    Απαντήσεις
    1. Για να γίνει σαφέστερο το εισαγωγικό επιχείρημα, προσθέτω μια λεπτομέρεια ουσίας: Όταν κάποιος παίκτης ξεκινάει τα παιχνίδια του στον β' γύρο, θεωρούμε ΧΒΓ ότι όλα τα παιχνίδια του β' γύρου μεταξύ των πάνω από αυτόν στην κατάταξη του α΄γύρου έχουν ολοκληρωθεί. Π.χ. όταν ξεκινάει ο τελευταίος του α΄γύρου τα παιχνίδια του στο β' γύρο, όλα τα παιχνίδια μεταξύ όλων των υπολοίπων στον β' γύρο, από τον πρώτο μέχρι τον προτελευταίο του α΄γύρου, έχουν γίνει. Το αντίστοιχο ισχύει για τον προτελευταίο του α΄γύρου κ.ο.κ.

      Διαγραφή
    2. Έτσι, για ν παίχτες, όταν ο τελευταίος του α΄γύρου τελειώσει τα παιχνίδια του στον β' γύρο , θα πρέπει να έχει ξεπεράσει στη βαθμολογία ν-1 παίχτες σε ν-1 παιχνίδια και προηγουμένως ο προτελευταίος του α΄γύρου να έχει ξεπεράσει ν-2 παίχτες σε ν-2 παιχνίδια κ.ο.κ.

      Διαγραφή
  2. Θα προσπαθήσω να διατυπώσω τις παραπάνω σκέψεις με πιο σύντομο, γενικό και μαθηματικά αυστηρό τρόπο.
    Σε ένα πρωτάθλημα με ν παίχτες, σε κάθε γύρο μοιράζονται ν(ν-1)/2 βαθμοί και συνολικά στους δύο γύρους ν(ν-1) βαθμοί.
    Για να υπάρξει τελικά πλήρης αντιστροφή της βαθμολογίας του α’ γύρου, θα πρέπει οι βαθμοί που θα συγκεντρώσει στον β΄γύρο ο δεύτερος του α’ γύρου να είναι κατά 1 τουλάχιστον περισσότεροι από όσους θα συγκεντρώσει ο πρώτος του α΄γύρου, οι βαθμοί που θα συγκεντρώσει ο τρίτος του α’ γύρου να είναι κατά 1 τουλάχιστον περισσότεροι από όσους θα συγκεντρώσει ο δεύτερος του α΄γύρου κ.ο.κ. Επομένως αν ο πρώτος του α’ γύρου συγκεντρώσει στον β΄γύρο β βαθμούς, όπου β≥0, θα πρέπει να ισχύει:
    β+(β+1)+(β+2)+….+(β+ν-1)≤ν(ν-1)/2 =>
    νβ+ν(ν-1)/2≤ν(ν-1)/2 => νβ≤0 => β=0
    Αν στον α’ γύρο ο πρώτος είχε συγκεντρώσει α βαθμούς, όπου α>0, τότε ο δεύτερος είχε συγκεντρώσει το πολύ α-0,5, ο τρίτος το πολύ α-1 κ.ο.κ. και ο τελευταίος το πολύ α-(ν-1)/2. Επομένως θα ισχύει:
    α+(α-0,5)+(α-1)+….[α-(ν-1)/2]≥ν(ν-1)/2 => να-(ν-1)/4≥ν(ν-1)/2 => α≥3(ν-1)/4 (1)
    Στην τελική βαθμολογία, ο πρώτος του α΄γύρου θα έχει α+β=α+0=α βαθμούς ακριβώς, ο δεύτερος του α΄γύρου τουλάχιστον α+0,5, ο τρίτος του α΄γύρου τουλάχιστον α+1 κ.ο.κ. και ο τελευταίος του α΄γύρου τουλάχιστον α+(ν-1)/2 βαθμούς, οπότε θα πρέπει να ισχύει:
    α+(α+0,5)+(α+1)+….+[α+(ν-1)/2]≤ν(ν-1) =>
    να+ν(ν-1)/4≤ν(ν-1) => α≤3(ν-1)/4 (2)
    Για να ισχύουν ταυτόχρονα οι σχέσεις (1) και (2), θα πρέπει α=3(ν-1)/4 => 4α=3(ν-1).
    Δεδομένου ότι ο α πρέπει να είναι υποχρεωτικά της μορφής 0,5*ακέραιος, ο 4α θα πρέπει να είναι άρτιος, άρα και ο ν-1 άρτιος, άρα ο ν περιττός.
    Αυτό εξηγεί γιατί στην περίπτωση ν=10 παιχτών το ζητούμενο είναι ανέφικτο, ενώ στην περίπτωση ν=9 είναι εφικτό με τον τρόπο που δείξαμε σε προηγούμενο σχόλιο.

    ΑπάντησηΔιαγραφή