Euler 2014-5

#1

Έστω θετικοί ακέραιοι k,n

και υποσύνολα $A_1,\ldots,A_{k}$ του [n]

ώστε
(α) $A_1 \cup \cdots \cup A_{k} = [n]$ ,
(β) |A_i|=3

για κάθε $i \in [k]$ ,
(γ) για κάθε δύο $x,y \in [n]$ με $x \neq y$ η δυάδα $\{x,y\}$ ανήκει είτε σε ακριβώς δύο είτε σε κανένα A_j

και
(δ) κάθε $x \in [n]$ ανήκει σε ακριβώς

από τα

.
Να βρεθούν όλες οι πιθανές τιμές του

.

[Όπου με [m]

συμβολίζω το σύνολο $\{1,2,\ldots,m\}$ .]

ksofsa · #2

Θεωρώ πίνακα με 3 γραμμές και k στήλες.
Στην πρώτη στήλη τοποθετώ τα στοιχεία του $A_{1}$ ,στη δεύτερη του $A_{2}$ κ.ό.κ.

Σύμφωνα με το δεδομένο (δ) τα στοιχεία του πίνακα είναι

.

Αρα

.

Κάθε στήλη περιέχει 3 δυάδες στοιχείων άρα όλος ο πίνακας

δυάδες.

Σύμφωνα με το δεδομένο (γ),οι δυάδες του πίνακα είναι άρτιος αριθμός.

Αρα 2/k

.

Σύμφωνα με τα παραπάνω το n είναι της μορφής n=6p

.

Θα αποδείξω ότι για κάθε n=6p

ικανοποιείται ο ισχυρισμός του προβλήματος.

Για n=6,k=10.

Τα υποσύνολα $A_{1}=(1,2,3),A_{2}=(1,2,4),A_{3}=(2,3,5),A_{4}=(1,4,5),A_{5}=(3,4,5),A_{6}=(1,5,6),A_{7}=(3,4,6),A_{8}=(2,5,6),A_{9}=(2,4,6),A_{10}=(1,3,6)$ ικανοποιούν τον ισχυρισμό του προβλήματος.

Για $n\geq 12$ ,τοποθετούμε τα πρώτα 6 στοιχεία του [n] στις 10 πρώτες στήλες του πίνακα όπως παραπάνω,τα επόμενα 6 στις επόμενες 10 στήλες με τον ίδιο τρόπο κ.ο.κ.

Τελικά n=6p

.

#3

Πολύ ωραία Κώστα. Ακριβώς έτσι την έλυσα και εγώ. Οπότε τέτοια άσκηση θα μπορούσε άνετα να τεθεί και σε μαθητικό διαγωνισμό. Βάζω όμως και την επίσημη λύση η οποία χρησιμοποιεί πιο ισχυρά υλικά.

Για κάθε $A_i = \{x_i,y_i,z_i\}$ θεωρούμε ένα «αφηρημένο» τρίγωνο x_iy_iz_i

. Αν δυο τρίγωνα έχουν κοινή πλευρά τότε τα κολλάμε μεταξύ τους. Οι συνθήκες (α)-(γ) μας λένε πως έχουμε μια τριγωνοποίηση με

κορυφές μιας κλειστής επιφάνειας

. Η επιφάνεια έχει V = n

κορυφές και F = k

έδρες. Επίσης αφού κάθε ακμή ανήκει σε ακριβώς δύο έδρες και κάθε έδρα έχει ακριβώς

ακμές παίρνουμε ότι 3F = 2E

. Τέλος με τον ίδιο τρόπο από την συνθήκη (δ) παίρνουμε 5V = 2E

.

Οπότε η επιφάνεια έχει χαρακτηριστική Euler $\chi(S) = V - E + F = V - E/3 = n/6$ και άρα 6|n

.

Για την κατασκευή για n=6

ψάχνουμε για μια τριγωνοποίηση (με έξι κορυφές) μιας επιφάνειας με χαρακτηριστική

. Οπότε ψάχνουμε για τριγωνοποίηση του πραγματικού προβολικού επιπέδου (real projective plane).

Παίρνουμε λοιπόν ένα εικοσάεδρο με δώδεκα κορυφές και δέκα έδρες και ταυτίζουμε τις αντίδιαμετρικές κορυφές. Οπότε όντως παίρνουμε τριγωνοποίηση του προβολικού επιπέδου με έξι κορυφές και όπου κάθε κορυφή ανήκει σε πέντε τρίγωνα.

Ασφαλώς για την κατασκευή για n = 6m

απλά

ξένες μεταξύ τους τριγωνοποιήσεις όπως πιο πάνω.

Euler 2014-5

Euler 2014-5

Re: Euler 2014-5

Re: Euler 2014-5

Μέλη σε σύνδεση