Τουρνουά Πόλεων - Άνοιξη 1980 Juniors

#1

Γενικά αυτός ο διαγωνισμός έχει πολύ έξυπνα προβλήματα. Κάνω αρχή με τα προβλήματα του πρώτου διαγωνισμού.

Κάποια από τα προβλήματα ίσως να τα έχουμε ξαναδεί. Όσοι τα ξέρουν ας περιμένουν 1-2 μέρες πριν να βάλουν την λύση (η να παραπέμψουν σε αυτή).

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

Αρχικά ξεκινάμε με δύο κόκκινα σημεία. Να δειχθεί ότι δεν υπάρχει ακολουθία κινήσεων ώστε να καταλήξουμε σε δύο μπλε σημεία.

Πρόβλημα 2: Έχουμε αριθμούς στα κελιά ενός $N \times N$ πίνακα έτσι ώστε όλες οι σειρές να είναι διαφορετικές. Να δειχθεί ότι μπορούμε να διαγράψουμε μια στήλη ώστε οι σειρές να εξακολουθούν να είναι διαφορετικές. (Θεωρούμε δυο σειρές/στήλες διαφορετικές ακόμη και αν διαφέρουν σε ένα στοιχείο.)

Πρόβλημα 3: Να βρεθούν όλες οι μεταθέσεις $a_1,\ldots,a_{101}$ των $2,3,\ldots,102$ ώστε το a_k

να διαιρείται με το

για κάθε

.

Πρόβλημα 4: Δίνεται ένα κυρτό τετράπλευρο ABCD

. Κάθε πλευρά του υποδιαιρείται σε

ίσα τμήματα. Συνδέουμε τα σημεία της διαίρεσης της πλευράς

με τα αντίστοιχα σημεία της πλευράς

με ευθύγραμμα τμήματα. Αυτά είναι το πρώτο σύνολο ευθυγράμμων τμημάτων. Κάνουμε το ίδιο με τα σημεία των

και

για να πάρουμε το δεύτερο σύνολο ευθυγράμμων τμημάτων. Δείτε π.χ. το σχήμα για την περίπτωση N=4

.

$\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm] \clip(-2.62,-1.9) rectangle (6.36,4.46); \draw [line width=1.6pt] (-1.58,3.58)-- (-0.82,-1.); \draw [line width=1.6pt] (-0.82,-1.)-- (4.36,-1.1); \draw [line width=1.6pt] (4.36,-1.1)-- (5.74,2.42); \draw [line width=1.6pt] (5.74,2.42)-- (-1.58,3.58); \draw [line width=1.6pt] (0.25,3.29)-- (0.475,-1.025); \draw [line width=1.6pt] (1.77,-1.05)-- (2.08,3.); \draw [line width=1.6pt] (3.91,2.71)-- (3.065,-1.075); \draw [line width=1.6pt] (-1.01,0.145)-- (4.705,-0.22); \draw [line width=1.6pt] (5.05,0.66)-- (-1.2,1.29); \draw [line width=1.6pt] (-1.39,2.435)-- (5.395,1.54); \draw (-2.,4.1) node[anchor=north west] {A}; \draw (5.62,3) node[anchor=north west] {B}; \draw (4.35,-0.99) node[anchor=north west] {C}; \draw (-1.38,-0.99) node[anchor=north west] {D}; \end{tikzpicture}$

Αυτό σχηματίζει N^2

μικρότερα τετράπλευρα. Από αυτά επιλέγουμε

ώστε κάθε δύο τετράπλευρα να χωρίζονται από κάποιο ευθύγραμμο τμήμα από το πρώτο σύνολο και κάποιο από το δεύτερο. Να δειχθεί ότι το άθροισμα των εμβαδών αυτών των τμημάτων ισούται με το εμβαδόν του ABCD

διαιρουμένου με το

.

Πρόβλημα 5: Έχουμε ένα πεπερασμένο σύνολο ευθυγράμμων τμημάτων συνολικού μήκους 18. Όλα τα τμήματα βρίσκονται μέσα σε ένα μοναδιαίο τετράγωνο. Τα τμήματα είναι παράλληλα στις πλευρές του τετραγώνου και επιτρέπεται να τέμνονται μεταξύ τους. Τα τμήματα χωρίζουν το μοναδιαίο τετράγωνο σε διάφορες περιοχές. Να δειχθεί ότι τουλάχιστον μια περιοχή έχει εμβαδόν τουλάχιστον 1/100

.

Επεξεργασία 1: Έγινε διόρθωση στην εκφώνηση του 2.
Επεξεργασία 2: Το σχήμα προστέθηκε σε tikz/latex

#2

Το πρόβλημα 2 το είδαμε και εδώ.

Νομίζω είχαμε δει και το πρόβλημα 4 αλλά δεν βρήκα τον σύνδεσμο. Επεξεργασία: Ίσως να θυμόμουν αυτό εδώ.

#3

Demetres έγραψε:
Πρόβλημα 3: Να βρεθούν όλες οι μεταθέσεις $a_1,\ldots,a_{101}$ των $2,3,\ldots,102$ ώστε το να διαιρείται με το για κάθε .

Θα δούμε πρώτα ότι στις θέσεις a_k

όπου ο

δεν διαιρεί το $102=2\cdot 3 \cdot 17$ , μπαίνει ο

. Με άλλα λόγια, με εξαίρεση τους 2,3,6,17,34,51,102

από τους δοθέντες, η μετάθεση είναι της μορφής

$a_1,\, a_2,\, a_3,\, a_4,\, a_5,\,a_6,\, a_7,\, a_8, \, ...\, , a_{16},\, a_{17}, \, a_{18}, \, ...\,, a_{101} =$

$a_1,\, a_2,\, a_3,\, 4,\, 5,\,a_6,\, 7,\, 8, \, ...\, , 16,\, a_{17}, \, 18, \, ...\, ,101$

Πράγματι, για $k=52,53, ... \, , 101$ ο

δεν διαιρεί κανέναν άλλον μεταξύ των $2,3,...\, 102$ πλην του εαυτού του. Άρα η συνθήκη k|a_k

δίνει $a_{52}=52, \, a_{53}=53,\, ...\,, a_{101}=101$ .

Επίσης για $k=35,\,...\, , 50$ ο

διαιρεί μόνο τον εαυτό του ή τον

(υπόψη

) αλλά ο

(που είναι από $70,\, ...\,, 100$ ) έχει ήδη χρησιμοποιηθεί. Άρα a_k=k

και σε αυτές τις περιπτώσεις.

Ακολουθούμε τον ίδιο συλλογισμό διαδοχικά για τους $k=18,\, ... \, , 33$ , μετά τους $k=9,...\, 16$ , μετά k=7,8

, μετά

. Σε κάθε περίπτωση πρέπει a_k=k

γιατί τα μεγαλύτερα πολλαπλάσια του

έχουν χρησιμοποιηθεί.

Συμπέρασμα: Η απάντηση στο πρόβλημά μας ανάγεται στο να βρούμε πόσες μεταθέσεις υπάρχουν με

$a_1 \in \{2,3,6,17,34,51,102\}$ και $a_2 \in \{2,6,34,102\}$ και $a_3 \in \{3,6,51,102\}$ και $a_6 \in \{6,102\}$ και $a_{17} \in \{17,34, 51,102\}$ και $a_{34} \in \{34,102\}$ και $a_{51} \in \{51,102\}$ (ενώ για τα υπόλοιπα είναι a_k=k

).

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

α) $a_1=102,\, a_2=2,\, a_3=3,\, a_{6}=6,\, a_{17}=17,\, a_{34}=34, \, a_{51}=51$

β) $a_1=17,\, a_2=2,\, a_3=3,\, a_{6}=6,\, a_{17}=34,\, a_{34}=102, \, a_{51}=51$

και ούτω καθ' εξής. Αν μέτρησα σωστά όλες τις περιπτώσεις (το έκανα δύο φορές) βρήκα

, που είναι η απάντηση στο πρόβλημά μας.

Φιλικά,

Μιχάλης

Edit: Διόρθωσα τις τυπογραφικές αβλεψίες που επισημαίνει ο Δημήτρης παρακάτω. Τον ευχαριστώ για την επισήμανση.

#4

Demetres έγραψε: Πρόβλημα 5: Έχουμε ένα πεπερασμένο σύνολο ευθυγράμμων τμημάτων συνολικού μήκους 18. Όλα τα τμήματα βρίσκονται μέσα σε ένα μοναδιαίο τετράγωνο. Τα τμήματα είναι παράλληλα στις πλευρές του τετραγώνου και επιτρέπεται να τέμνονται μεταξύ τους. Τα τμήματα χωρίζουν το μοναδιαίο τετράγωνο σε διάφορες περιοχές. Να δειχθεί ότι τουλάχιστον μια περιοχή έχει εμβαδόν τουλάχιστον .

Έστω ότι το τετράγωνο χωρίζεται σε

περιοχές. Για $\displaystyle{i \in \left\{ {1,2, \ldots ,n} \right\},}$ συμβολίζουμε με $\displaystyle{{E_i}}$ το εμβαδόν και με $\displaystyle{{P_i}}$ την περίμετρο της

-στής περιοχής.

Υποθέτουμε ότι $\displaystyle{{E_i} < \frac{1}{{100}}}$ για κάθε $\displaystyle{i \in \left\{ {1,2, \ldots ,n} \right\}.}$

Θεωρούμε το ελάχιστο ορθογώνιο $\displaystyle{{R_i},}$ με διαστάσεις $\displaystyle{{x_i},{y_i},}$ που περιγράφεται στην

-στή περιοχή. Τότε, ισχύουν οι ανισότητες:

$\displaystyle{{E_i} \le {x_i}{y_i}}$

και

$\displaystyle{{P_i} \ge 2\left( {{x_i} + {y_i}} \right)}$

για κάθε $\displaystyle{i \in \left\{ {1,2, \ldots ,n} \right\}.}$

Χρησιμοποιώντας την υπόθεσή μας και την ανισότητα αριθμητικού-γεωμετρικού μέσου βρίσκουμε ότι:

$\displaystyle{1 = \sum\limits_{i = 1}^n {{E_i}} = \sum\limits_{i = 1}^n {\sqrt {{E_i}} } \sqrt {{E_i}} < \frac{1}{{10}}\sum\limits_{i = 1}^n {\sqrt {{E_i}} } \le \frac{1}{{10}}\sum\limits_{i = 1}^n {\sqrt {{x_i}{y_i}} } \le }$

$\displaystyle{ \le \frac{1}{{10}}\sum\limits_{i = 1}^n {\frac{{{x_i} + {y_i}}}{2}} = \frac{1}{{40}}\sum\limits_{i = 1}^n {2\left( {{x_i} + {y_i}} \right)} \le \frac{1}{{40}}\sum\limits_{i = 1}^n {{P_i}} = \frac{1}{{40}}\left( {4 + 2 \cdot 18} \right) = 1.}$

Αυτό όμως είναι άτοπο, οπότε το ζητούμενο δείχθηκε.

#5

Mihalis_Lambrou έγραψε: Συμπέρασμα: Η απάντηση στο πρόβλημά μας ανάγεται στο να βρούμε πόσες μεταθέσεις υπάρχουν με

$a_1 \in \{1,2,3,6,17,34,51,102\}$ και $a_2 \in \{2,6,34,102\}$ και $a_3 \in \{3,6,51,102\}$ και $a_6 \in \{6,102\}$ και $a_{17} \in \{17,51,102\}$ και $a_{34} \in \{34,102\}$ και $a_{51} \in \{51,102\}$ (ενώ για τα υπόλοιπα είναι ).

Αυτές τις μετράμε με το χέρι. Δυστυχώς δεν βρίσκω οικονομικό τρόπο καταμέτρησης.

Ωραία Μιχάλη. (Υπάρχουν κάποια μικρά τυπογραφικά. Π.χ. $1 \notin a_1$ και $34 \in a_{17}$ .) Μπορούμε να καταγράψουμε αυτές τις μεταθέσεις ως εξής.

Έστω $k_1 =1, k_2,\ldots,k_r$ οι δείκτες για τους οποίους $a_k \neq k$ . Πρέπει

$\{a_{k_1},\ldots,a_{k_r}\} = \{k_2,\ldots,k_r,102\}$

και επειδή για αυτούς τους δείκτες είναι a_k > k

πρέπει

$a_{k_r} = 102, a_{k_{r-1}} = k_r, \ldots,a_{k_1} = k_2$ .

Τότε όμως έχουμε $k_1|k_2,k_2|k_3,\ldots,k_{r-1}|k_r,k_r|102$ .

Επειδή $102 = 2 \times 3 \times 17$ μπορούμε τώρα να κάνουμε μια πιο συστηματική καταγραφή ως εξής:

Για k_1 = 2

, έχουμε τις ακολουθίες $2,102; \quad 2,6,102; 2,34;102$ .
Για k_1 = 3

και

πάλι έχουμε από τρεις ακολουθίες.
Για k_1=6,34

ή

έχουμε από

ακολουθία. Το ίδιο και για k_1=102

.

Άρα συνολικά έχουμε όντως 13 ακολουθίες.

#6

Demetres έγραψε:
Πρόβλημα 1: Στην περιφέρεια ενός κύκλου υπάρχουν κόκκινα και μπλε σημεία. Κάποιος μπορεί να προσθέσει ένα κόκκινο σημείο και να αλλάξει το χρώμα των δύο γειτονικών του σημείων ή να αφαιρέσει ένα κόκκινο και να αλλάξει το χρώμα των δύο γειτονικών του σημείων.

Αρχικά ξεκινάμε με δύο κόκκινα σημεία. Να δειχθεί ότι δεν υπάρχει ακολουθία κινήσεων ώστε να καταλήξουμε σε δύο μπλε σημεία.

Νομίζω αρκετά δύσκολη. Δίνω μια βοήθεια:

Ορίζω την ακολουθία $a_1,a_2,\ldots$ ως εξής: Ξεκινάμε με a_1

κόκκινα σημεία, μετά έχουμε ένα μπλε, μετά a_2

κόκκινα, μετά ένα μπλε κ.τ.λ.

Π.χ. στην αρχική διάταξη η ακολουθία είναι η

. Στην διάταξη ΜΚΜΜΚΚΚΚΜ η ακολουθία είναι η 0,1,0,4,0

.

Δείτε πως αλλάζει αυτή η ακολουθία με κάθε κίνηση.

Τουρνουά Πόλεων - Άνοιξη 1980 Juniors

Τουρνουά Πόλεων - Άνοιξη 1980 Juniors

Re: Τουρνουά Πόλεων - Άνοιξη 1980 Juniors

Re: Τουρνουά Πόλεων - Άνοιξη 1980 Juniors

Re: Τουρνουά Πόλεων - Άνοιξη 1980 Juniors

Re: Τουρνουά Πόλεων - Άνοιξη 1980 Juniors

Re: Τουρνουά Πόλεων - Άνοιξη 1980 Juniors

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