Ν σημεία σε έναν κύκλο

Κυριάκος Τσουρέκας · #1

Δεν είναι δική μου...:

Υπάρχουν

σημεία σε έναν κύκλο, έτσι ώστε κάθε ευθύγραμμο τμήμα που ενώνει δύο σημεία να είναι είτε μπλε ή κόκκινο. Δίνεται επίσης ότι τα P_iP_j

και $P_{i+1} P_{j+1}$ είναι διαφορετικού χρώνατος, για κάθε i, j

στο $\left\{1, 2, ..., n\right\}$ .
α) Για ποιές τιμές του

είναι δυνατός ένας τέτοιος χρωματισμός;
β) Δείξτε ότι μπορούμε να πάμε από κάθε σημείο σε οποιοδήποτε άλλο με το πολύ 3 βήματα, όπου ένα βήμα μεταξύ δύο σημείων που ενώνονται με κόκκινο χρώμα.

Edit: ελπίζω να είναι στο σωστό φάκελο...

#2

Κυριάκος Τσουρέκας έγραψε: ↑
Σάβ Αύγ 06, 2022 6:43 pm
Δίνεται επίσης ότι τα και $P_{i+1} P_{j+1}$ είναι διαφορετικού χρώνατος, για κάθε στο $\left\{1, 2, ..., n\right\}$ .

Θεωρώ ότι οι δείκτες είναι modulo n.

Ισχυρίζομαι ότι ο χρωματισμός είναι δυνατός αν και μόνο αν το

είναι πολλαπλάσιο του

:

Αν

περιττός και P_1P_2

μπλε, τότε επαγωγικά $P_iP_{i+1}$ είναι μπλε αν

περιττός και κόκκινο αν

άρτιος. Αυτό όμως είναι άτοπο αφού θα είχαμε $P_1P_2 = P_{2m+2}P_{2m+3}$ κόκκινο.

Αν n = 4m+2

περιττός και $P_1P_{2m+2}$ μπλε, τότε επαγωγικά $P_iP_{i+2m+1}$ είναι μπλε αν

περιττός και κόκκινο αν

άρτιος. Αυτό όμως είναι άτοπο αφού θα είχαμε $P_1P_{2m+2} = P_{2m+2}P_{4m+3}$ κόκκινο.

Αν n = 4m

τότε επιλέγω αυθαίρετα το χρώμα των $P_1P_2,P_1P_3,\ldots,P_1P_{2m+1}$ . Κάθε τμήμα μπορώ να το γράψω στη μορφή $P_iP_{k+i}$ με $k \in \{1,2,\ldots,2m\}$ . Το τμήμα θα έχει το ίδιο χρώμα με την $P_1P_{1+k}$ αν

περιττός και διαφορετικό αν

είναι άρτιος. Είναι άμεσο ότι αυτό είναι συμβατό με τις συνθήκες. (Διότι η γραφή σε αυτή τη μορφή είναι μοναδική εκτός και αν k=2m

. Όμως τα $P_iP_{2m+i} = P_{2m+i}P_{4m+i}$ έχουν το ίδιο χρώμα όπως θα έπρεπε.)

Αυτό κλείνει το (α). Μάλιστα έχουμε βρει όλους τους τρόπους που μπορεί να γίνει ο χρωματισμός στην περίπτωση όπου αυτό είναι δυνατό.

Για το (β) αρκεί να δείξουμε πως μπορούμε να πάμε από το 1 στο $i \in \{2,3,\ldots,4m\}$ σε τρία το πολύ βήματα.

Περίπτωση 1: i = 2r+1

. Αν $P_1P_{2r+1}$ κόκκινο τότε είμαστε εντάξει. Ας υποθέσουμε λοιπόν ότι $P_1P_{2r+1}$ μπλε. Τότε τα $P_2P_{2r+2}$ και $P_{4m}P_{2r}$ είναι αναγκαστικά κόκκινα.

Αν P_1P_2

κόκκινο τότε και το $P_{2r+1}P_{2r+2}$ είναι κόκκινο και μπορούμε να κάνουμε τα κόκκινα βήματα $P_1 \rightarrow P_2 \rightarrow P_{2r+2} \rightarrow P_{2r+1}$ .

Σε διαφορετική περίπτωση είναι $P_1P_{4m}$ κόκκινο. Τότε και το $P_{2r}P_{2r+1}$ είναι κόκκινο και μπορούμε να κάνουμε τα κόκκινα βήματα $P_1 \rightarrow P_{4m} \rightarrow P_{2r} \rightarrow P_{2r+1}$ .

Περίπτωση 2: i = 2r

. Αν $P_1P_{2r}$ κόκκινο τότε είμαστε εντάξει. Ας υποθέσουμε λοιπόν ότι $P_1P_{2r}$ μπλε. Τότε τα $P_{2r}P_{4r-1}$ και $P_{4m+2-2r}P_{1}$ είναι αναγκαστικά κόκκινα. Αν $P_{2r}P_{4m+2-2r}$ κόκκινο τότε τελειώσαμε με τα κόκκινα βήματα $P_1 \rightarrow P_{4m+2-2r} \rightarrow P_{2r}$ . Σε διαφορετική περίπτωση το $P_1P_{4r-1}$ είναι κόκκινο και τελειώσαμε με τα κόκκινα βήματα $P_1 \rightarrow P_{4r-1} \rightarrow P_{2r}$ .

Ν σημεία σε έναν κύκλο

Ν σημεία σε έναν κύκλο

Re: Ν σημεία σε έναν κύκλο

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