Στην διαγαλαξιακή αυτοκρατορία υπάρχουν $10^{2015}$ πλανήτες, οποιοιδήποτε δύο από τους οποίους συνδέονται με μια κοσμική γραμμή διπλής κατεύθυνσης. Αυτές οι συνδέσεις εξυπηρετούνται από $2015$ μεταφορικές εταιρείες.
Ο αυτοκράτορας θέλει να κλείσει $k$ από αυτές τις εταιρίες έτσι, ώστε, χρησιμοποιώντας τις υπόλοιπες να μπορεί κάποιος να βρει τρόπο να μεταφερθεί από οποιοδήποτε πλανήτη σε κάποιον άλλο. Για ποιο μέγιστο $k$ με σιγουριά μπορεί να επιτευχθεί ένα τέτοιο πλάνο;
Μαθηματική Ολυμπιάδα Αγίας Πετρούπολης
Διαμερίζουμε τις 2015 εταιρίες σε δύο ξένα μεταξύ τους υποσύνολα Υ1 και Υ2. Αν ΧΒΓ υποθέσουμε ότι υπάρχει ζευγάρι πλανητών (α,β) που δεν συνδέονται άμεσα ή μέσω τρίτου πλανήτη αποκλειστικά μέσω εταιριών του Υ1, αυτό θα σημαίνει ότι αφενός οι πλανήτες α, β συνδέονται άμεσα αποκλειστικά μέσω εταιριών του συνόλου Υ2 και αφετέρου ότι δεν υπάρχει τρίτος πλανήτης γ για τον οποίο οι άμεσες συνδέσεις (α,γ) και (β,γ) εξυπηρετούνται αμφότερες (όχι κατανάγκην αποκλειστικά) από εταιρείες του Υ1. Στην περίπτωση αυτή η μία τουλάχιστον από τις συνδέσεις (α,γ) ή (β,γ) θα εξυπηρετείται επίσης αποκλειστικά μέσω εταιριών του Υ2. Έτσι όμως θα μπορούσαμε να μετακινηθούμε αποκλειστικά μέσω εταιριών του Υ2 αφενός μεταξύ α και β (άμεσα), αλλά και από κάθε πλανήτη γ τόσο στον α όσο και στον β (ή ανάποδα), είτε άμεσα είτε μέσω ενός από τους α ή β. Σε κάθε περίπτωση και ανεξαρτήτως αριθμού πλανητών, μπορούν να κλείσουν με ασφάλεια όλες οι εταιρείες του Υ1 ή διαζευκτικά του Υ2, ήτοι τουλάχιστον 1007 εταιρίες (για κ=1007 ή 1008).
ΑπάντησηΔιαγραφήΔεν μπορούν όμως να κλείσουν με ασφάλεια 1008 ή περισσότερες, γιατί δεν αποκλείεται η περίπτωση κάθε πλανήτης να εξυπηρετείται αποκλειστικά από ένα υποσύνολο των 2015 εταιρειών, που περιλαμβάνει 1008 ακριβώς εταιρίες και κάθε ομάδα 1008 εταιριών να είναι το υποσύνολο εξυπηρέτησης ενός τουλάχιστον πλανήτη (δεδομένου ότι οι 10^2015 πλανήτες είναι περισσότεροι από τα C(2015,1008) 1008μελή υποσύνολα εταιριών). Για κάθε δύο πλανήτες, τα αντίστοιχα υποσύνολα έχουν μία ή περισσότερες κοινές εταιρίες (δεδομένου ότι 1008 εταιρίες είναι περισσότερες από τις μισές των 2015), επομένως δεν αποκλείεται κάθε δύο πλανήτες να συνδέονται άμεσα μεταξύ τους μόνο μέσω των κοινών εταιριών εξυπηρέτησής τους. Σε αυτή την περίπτωση, οποιεσδήποτε 1008 εταιρίες κι αν κλείσουν, αυτές θα είναι το υποσύνολο εταιριών ενός τουλάχιστον πλανήτη και ο πλανήτης αυτός δεν θα συνδέεται πλέον άμεσα με κανέναν άλλον πλανήτη.
Επομένως δεν μπορούν να κλείσουν με ασφάλεια περισσότερες από 1007 εταιρίες.
Χρόνια πολλά, ευτυχισμένος ο καινούργιος χρόνος για όλους τους φίλους!