Περιπολικά

[MoV]

Μια κυκλική πόλη ακτίνας 6km ελέγχεται από 18 περιπολικά που επικοινωνούν με ασύρματο . Αν η ακτίνα δράσης του ασυρμάτου είναι 9km δείξτε ότι :
i)πάντα θα υπάρχουν 2 περιπολικά που το καθένα θα επικοινωνεί με τουλάχιστον 5 περιπολικά
ii)πάντα θα υπάρχουν 8 περιπολικά που το καθένα θα επικοινωνεί με τουλάχιστον 5 περιπολικά
Είναι δυνατόν να υπάρχουν πάντα 9 ή περισσότερα περιπολικά που το καθένα να επικοινωνεί με τουλάχιστον 5 περιπολικά ?

Σημείωση : προφάνως το ii) συνεπάγεται το i) , άλλα επειδή η πρωτογενής μορφή της άσκησης περιλάμβανε μόνο το i) θα ήθελα να δω ποιά είναι η ιδέα που ταιριάζει στη λύση του i) .

[GVlachos]

Από το κέντρο του κύκλου φέρουμε ακτίνες που ανά δύο σμηματίζουν γωνία 120 μοιρών, σχηματίζοντας έτσι τρία χωρία. Τα περιπολικά που βρίσκονται στι εσωτερικό ή πάνω στα όρια ενός χωρίου επικοινωνούν μεταξύ τους. Αν ένα χωρίο περιέχει 8 τουλάχιστον περιπολικά, τότε κάθε ένα από αυτά επικοινωνεί με τουλάχιστον 7 άλλα και τελειώσαμε. Αλλιώς θα υπάρχουν τουλάχιστον δύο χωρία με 6 τουλάχιστον περιπολικά (αφού 5+5+7=17), οπότε και πάλι τελειώσαμε.
Κατασκευάζοντας ένα ισόπλευρο τρίγωνο με κορυφές πάνω στον κύκλο και τοποθετώντας στις κορυφές του 5,5 και 8 περιπολικά, βλέπουμε ότι είναι δυνατόν να έχουμε ακριβώς 8 περιπολικά το καθένα από τα οπία επικοινωνεί με τουλάχιστον 5 ακόμα.

[MoV]

Από το κέντρο του κύκλου φέρουμε ακτίνες που ανά δύο σμηματίζουν γωνία 120 μοιρών, σχηματίζοντας έτσι τρία χωρία. Τα περιπολικά που βρίσκονται στι εσωτερικό ή πάνω στα όρια ενός χωρίου επικοινωνούν μεταξύ τους. Αν ένα χωρίο περιέχει 8 τουλάχιστον περιπολικά, τότε κάθε ένα από αυτά επικοινωνεί με τουλάχιστον 7 άλλα και τελειώσαμε. Αλλιώς θα υπάρχουν τουλάχιστον δύο χωρία με 6 τουλάχιστον περιπολικά (αφού 5+5+7=17), οπότε και πάλι τελειώσαμε.
Κατασκευάζοντας ένα ισόπλευρο τρίγωνο με κορυφές πάνω στον κύκλο και τοποθετώντας στις κορυφές του 5,5 και 8 περιπολικά, βλέπουμε ότι είναι δυνατόν να έχουμε ακριβώς 8 περιπολικά το καθένα από τα οπία επικοινωνεί με τουλάχιστον 5 ακόμα.

Το bold είναι λανθασμένο διότι η μέγιστη απόσταση μέσα στα χωρία που περιγράφεις είναι .
Κατά τα άλλα απαντάς σωστά στο 3ο σκέλος της άσκησης .

[GVlachos]

Ας το ξαναδούμε τότε.

Επειδή κάθε περιπολικό στο κέντρο του κύκλου θα επικοινωνεί με όλα τα υπόλοιπα, μπορούμε να υποθέσουμε ότι κανένα δεν βρίσκεται στο κέντρο.Φέρουμε τώρα τις ακτίνες που περιέχουν καθένα από τα περιπολικά. Ονομάζουμε τις ακτίνες διαδοχικά . Παρατηρούμε ότι αν φερουμε την κάθετη διάμετρο σε μια ακτίνα , τότε στο ημικύκλιο που περιέχει την ακτίνα όλα τα περιπολικά επικοινωνούν με το περιπολικό .Παίρνουμε ένα περιπολικό που επικοινωνεί με 4 το πολύ άλλα περιπολικά.Υπάρχει λοιπόν ένα ημικύκλιο που περιέχει 13 τουλάχιστον περιπολικά.Φέρουμε την κάθετη στη διάμετρο του ημικυκλίου ακτίνα.Αυτή το χωρίζει σε δύο χωρία, η μέγιστη απόσταση σε καθένα από τα οποία είναι μικρότερη του 9 από το νόμο των συνημιτόνων. Άρα αν σε ένα χωρίο έχουμε 8 τουλάχιστον σημεία τελειώσαμε, αλλιώς στο ένα θα έχουμε 6 και στο άλλο 7 οπότε και πάλι τελειώσαμε.

Συγγνώμη για το λάθος πιο πάνω. Πιστεύω ότι αυτή η λύση είναι σωστή.
Ωραίο πρόβλημα πάντως. Είναι από κάποιο διαγωνισμό?

[MoV]

Σαν άσκηση , που αφορά την αρχή του Περιστερεώνα , μου δόθηκε το i) . Στην προσπάθεια μου να την αντιμετοπίσω κατέληξα στα άλλα δύο ερωτήματα . Εξακολουθώ να ψάχνω μια κομψή εφαρμογή της αρχής του Περιστερεώνα που να αποδεικνύει το i) .

[Demetres]

Ωραία η λύση του Γιώργου και πιο σύντομη από την δική μου. Βάζω όμως και την δική μου μιας και χρησιμοποιεί διαφορετική μεθοδολογία:

Η λύση αποτελείται από το γεωμετρικό κομμάτι και το συνδυαστικό κομμάτι.

Στο γεωμετρικό κομμάτι θα δείξουμε ότι σε κάθε τέσσερα περιπολικά υπάρχουν δύο τα οποία επικοινωνούν: Ισχυρίζομαι αρχικά ότι σε κάθε τέσσερα περιπολικά υπάρχουν τρία που σχηματίζουν γωνία μεγαλύτερη ή ίση των 90 μοιρών. Πράγματι αν τρία από αυτά βρίσκονται στην ίδια ευθεία αυτό είναι άμεσο. Αν όχι, τότε κοιτάμε την κυρτή θήκη που σχηματίζουν. Αν είναι τετράπλευρο, τότε μία από τις γωνίες είναι μεγαλύτερη ή ίση από 90 μοίρες. Αν είναι τρίγωνο έστω , τότε το τέταρτο περιπολικό βρίσκεται στο εσωτερικό του τριγώνου και μια από τις γωνίες είναι μεγαλύτερη ή ίση από 120 μοίρες αφού το άθροισμά τους είναι 360 μοίρες.

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

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

Έστω ότι έχουμε ήδη βρει μια λίστα με περιπολικά τα οποία επικοινωνούν με τουλάχιστον άλλα πέντε περιπολικά. Θα δείξουμε ότι υπάρχει άλλο ένα τέτοιο. Ας απομονώσουμε λοιπόν 11 από τα περιπολικά τα οποία δεν ανήκουν στην λίστα.

Υποθέτουμε πρώτα ότι υπάρχουν τρία από αυτά τα 11 περιπολικά τα οποία δεν επικοινωνούν μεταξύ τους, έστω τα Α,Β,Γ. Τώρα κάθε ένα από τα 15 υπόλοιπα περιπολικά πρέπει να επικοινωνεί με τουλάχιστον ένα από τα Α,Β,Γ. Άρα τουλάχιστον ένα από τα Α,Β,Γ θα επικοινωνεί με τουλάχιστον άλλα πέντε περιπολικά. Αυτό το περιπολικό δεν ανήκε στην αρχική λίστα οπότε μπορούμε να το προσθέσουμε.

Μένει τώρα να δούμε τι συμβαίνει όταν σε αυτά τα 11 περιπολικά, για κάθε τρία από αυτά υπάρχουν δύο που επικοινωνούν μεταξύ τους. Ας πάρουμε ένα περιπολικό Α. Αν επικοινωνεί με άλλα πέντε περιπολικά τότε τελειώσαμε. Αν όχι τότε τουλάχιστον έξι από τα έντεκα περιπολικά δεν επικοινωνούν με το Α. Όμως από την υπόθεση, όλα αυτά πρέπει να επικοινωνούν μεταξύ τους οπότε πάλι τελειώσαμε.

[GVlachos]

Κύριε Δημήτρη μου άρεσε πολύ και η δική σας λύση, από την οποία χρήσιμη σε αρκετά προβλήματα συνδυαστικής είναι η ιδέα ότι αν έχουμε λιγότερα από 8 περιπολικά, μπορούμε να προσθέσουμε άλλο ένα, η οποία ουσιαστικά λύνει αυτό το πρόβλημα της IMO 2003:
viewtopic.php?f=50&t=13152.
Ας δει κάποιος το πρόβλημα αυτό που έχει μείνει πολύ καιρό άλυτο.