Συνδυαστικό θέμα!

[nickthegreek]

Έστω δοσμένες ευθείες στο επίπεδο, ανά δύο μη παράλληλες και ανά τρεις μη συντρέχουσες.Για ποιά k μπορεί κάποιος να "βαφτίσει"

με τα σημεία τομής όλων των ευθειών έτσι ώστε σε κάθε ευθεία όλες οι ταμπέλες από 1 έως k-1 να εμφανίζονται ακριβώς μία φορά;;;


Φιλικά,
Νίκος

[Cauchy-Schwartz]

Θα αποδείξουμε ότι αυτό είναι δυνατό για κ άρτιο.

Αν τέτοιο βάφτισμα υπάρχει, η ταμπέλα 1 πρέπει να προκύπτει σε κάθε γραμμή και κάθε σημείο βαπτισμένο 1 σε δύο γραμμές.
Συνεπώς, το πλήθος των κ είναι κ/2 και έτσι ο κ πρέπει να είναι άρτιος.

Από την άλλη, υποθέτουμε τον κ άρτιο.Τοποθετούμε τους αριθμούς 1,2,3,...,κ-1 σε κορυφές κανονικού (κ-1)-γώνου και τον κ στο κέντρο του.Τώρα, σημειώνουμε τα σημεία τομής όπως θα αναφέρουμε.
Το σημείο τομής της l_k και της l_m δίνει την ταμπέλα m = 1,2,...,k-1.Αν i, j<k, τότε το σημείο τομής της l_i και της ell_j δίνει την ταμπέλα m, όπου το τμήμα από το κ στο m είναι κάθετο στη διαγώνιο του (κ-1)-γώνου ανάμεσα του i και j.
Εύκολα ελέγχουμε ότι δεν υπάρουν δύο σημεία στην ίδια γραμμή που να δίνουν την ίδια ταμπέλα.

[Demetres]

Να προσθέσω ότι η άσκηση δεν είναι γεωμετρική αλλά είναι θεωρίας γραφημάτων. Μεταφράζοντάς την σε θεωρία γραφημάτων έχουμε:

Ένα πλήρες γράφημα με κορυφές. (Κάθε κορυφή αντιστοιχεί σε μία ευθεία. Πλήρες γράφημα θα πει ότι μεταξύ κάθε δυο κορυφών υπάρχει μία ακμή. Αυτή η ακμή αντιστοιχεί στο σημείο τομής των δυο ευθειών που αντιστοιχούν στις κορυφές.) Θέλουμε σε κάθε ακμή να γράψουμε ένα νούμερο από το 1 ως το ώστε για κάθε κορυφή, αν κοιτάξουμε όλες τις ακμές που προσπίπτουν σε αυτήν την κορυφή να εμφανίζονται όλα τα νούμερα (ακριβώς από μία φορά).

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

Το αποτέλεσμα που απέδειξε ο Cauchy-Schwarz λέει ότι αυτό γίνεται αν και μόνο αν το είναι άρτιος.