Demetres έγραψε:Demetres έγραψε:Ζητήθηκαν ασκήσεις συνδυαστικής και γεωμετρίας. Ας δώσω 2 σε 1.
ΑΣΚΗΣΗ 8: Δίνονται
ευθείες στο επίπεδο οι οποίες το διαμερίζουν σε κάποια χωρία. Έστω
ο μέγιστος αριθμός από αυτά τα χωρία ώστε ανά δύο να μην είναι γειτονικά. (Επιτρέπεται να έχουν κοινή κορυφή αλλά όχι κοινό ευθύγραμμο τμήμα.) Να δειχθεί ότι
Βοήθεια: Έστω
αυτά τα χωρία. Μετρήστε με δυο διαφορετικούς τρόπους τα ζεύγη
όπου η ευθεία
είναι μια από τις πλευρές του
. Είναι πιο απλό να δείξετε ότι
.
Λογάριαζα να ανεβάσω την λύση μου χθες, παραμονή του διαγωνισμού αλλά ξεχάστηκα.
Μετράω τα ζεύγη
όπως πιο πάνω. Αν για κάποιο
υπάρχει μόνο ένα
τότε όλες οι ευθείες είναι παράλληλες οπότε
αφού
.
Μπορώ λοιπόν να υποθέσω πως για κάθε
υπάρχουν τουλάχιστον δύο
και άρα ο αριθμός των ζευγών είναι τουλάχιστον
. Από την άλλη κάθε
διαμερίζεται σε
ευθύγραμμα τμήματα (ή ημιευθείες) από τις υπόλοιπες ευθείες. Κάθε τέτοιο τμήμα ανήκει το πολύ σε ένα
αφού τα
είναι ανά δύο μη γειτονικά. Άρα για κάθε
υπάρχουν το πολύ
και άρα ο συνολικός αριθμός ζευγών είναι το πολύ
.
Αυτό δίνει το πιο απλό
. Για το
ας ονομάζουμε με
τον αριθμό των
για τα οποία υπάρχουν ακριβώς δύο
. Τότε και οι δύο πλευρές του
είναι ημιευθείες και επειδή ακριβώς
ημιευθείες υπάρχουν το πολύ
τέτοια
. Κάθε άλλο από τα
χρησιμοποιεί τουλάχιστον τρία
και άρα ο συνολικός αριθμός ζευγών είναι τουλάχιστον
. Οπότε
που δίνει το ζητούμενο.