JBMO Shortlist 2019 - Συνδυαστική

#1

Η παρούσα ανάρτηση θα ανανεωθεί αργότερα και με τα υπόλοιπα προβλήματα.

C1. Έστω ένα σύνολο

από

θετικούς ακεραίους οι οποίοι έχουν την εξής ιδιότητα:

«Για κάθε τέσσερις αριθμούς του

, υπάρχει ένας ο οποίος διαιρεί κάθε ένα από τους άλλους τρεις ή υπάρχει ένας ο οποίος ισούται με το άθροισμα των άλλων τριών.»

Να δειχθεί ότι το σύνολο

περιέχει έναν αριθμό ο οποίος διαιρεί και τους

άλλους αριθμούς του

.

(Προτάθηκε από το Τατζικιστάν)

C2. Σε μια πόλη υπάρχουν

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

(Προτάθηκε από τη Σερβία)

#2

Επαναφορά με παράλληλο ανέβασμα και της C2.

Manolis Petrakis · #3

Καλησπέρα!
Μία απόδειξη για το C1
Έστω ότι $a_1,a_2,...,a_{100}$ οι αριθμοί με $a_1\leq a_2\leq ... \leq a_{100}$ .
●Αν δεν υπάρχει a_i

τέτοιος ώστε να ισχύει ότι:
a_1/a_2, a_1/a_3, a_1/a_i

τότε

για κάθε

. Έτσι είναι $a_4=a_5=...=a_{100}$ . Επομένως για την τετράδα (a_1, a_2, a_i, a_j)

είναι αδύνατον το άθροισμα των 3 αριθμών να ισόύται με τον 4ο, επομένως: a_1/a_2, a_1/a_i=a_j

. Όμοια με την τετράδα (a_1, a_3, a_i, a_j)

παίρνουμε ότι a_1/a_3

από όπου παίρνουμε το ζητούμενο.
●Αν υπάρχει a_k

τέτοιος ώστε να ισχύει ότι:
a_1/a_2, a_1/a_3, a_1/a_k

τότε για κάθε τετράδα (a_1, a_2, a_3, a_i)

ισχύει ότι (Είτε αν a_i=a_1+a_2+a_3

, είτε αν

):
$a_1\equiv a_2 \equiv a_3 \equiv 0(moda_1) \Rightarrow a_i\equiv0(moda_1)$ $\Leftrightarrow a_1/a_i$ για κάθε i=4,5,...100

από όπου παίρνουμε το ζητούμενο.

#4

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

Manolis Petrakis · #5

Demetres έγραψε: ↑
Δευ Οκτ 19, 2020 10:56 am
Σωστά για το C1. Ας τη δυσκολέψουμε λίγο: Να αποδειχθεί το ίδιο ακόμη και αν δεν γνωρίζουμε ότι οι αριθμοί είναι θετικοί.

Αν $a_1,a_2,...,a_{100}\in\mathbb{Z}$ και
$|a_1|\leq |a_2| \leq ... \leq |a_{100}|$ τότε
●Αν υπάρχει τετράδα (a_1,a_j,a_k,a_n)

τέτοια ώστε a_1/a_j,a_1/a_k,a_1/a_n

τότε για κάθε τετράδα (a_1,a_j,a_k,a_i)

είναι

ή
$a_1\equiv a_j\equiv a_k\equiv 0(moda_1)$ άρα $a_i\equiv 0(moda_1)\Leftrightarrow a_1/a_i$ για κάθε i=2,3,...,100

●Αν δεν υπάρχει τετράδα (a_1,a_j,a_k,a_n)

τέτοια ώστε a_1/a_j,a_1/a_k,a_1/a_n

•1η περίπτωση: υπάρχουν τουλάχιστον 5 ομόσημοι του a_1

, έστω

με $|a_k|\leq |a_i|\leq |a_m|\leq |a_n| \leq |a_j|$ . Τότε:
a_1+a_k+a_i=a_m

ομοίως

και για την τετράδα (a_1,a_j,a_n,a_m)

είναι αδύνατον να ισχύει ότι το άθροισμα των 3 αριθμών ισούται με τον 4ο
Έτσι $a_1/a_j=a_n=a_m\Rightarrow$ για κάθε τετράδα a_1,a_j,a_n,a_s

είναι $a_1\equiv a_j\equiv a_n\equiv 0(moda_1)$ άρα $a_s\equiv 0(moda_1)\Rightarrow a_1/a_s$ με s=2,3,...,100

•2η περίπτωση: υπάρχουν το πολύ 4 ομόσημοι αριθμοί του $a_1\Leftrightarrow$ τουλάχιστον 95 ετερόσημοι αριθμοί του a_1

. Έστω

η μικρότερη απόλυτη τιμή αριθμού, ετερόσημου του a_1

.
Έτσι όμοια με προηγουμένως:
$a_1\equiv a_2 \equiv ... \equiv a_{100}\equiv 0(moda_i)$
Αλλά $|a_ i|\geq|a_1|\Leftrightarrow |a_1|=|a_i|\Leftrightarrow a_1/a_s$ με s=2,3,...,100

JBMO Shortlist 2019 - Συνδυαστική

JBMO Shortlist 2019 - Συνδυαστική

Re: JBMO Shortlist 2019 - Συνδυαστική

Re: JBMO Shortlist 2019 - Συνδυαστική

Re: JBMO Shortlist 2019 - Συνδυαστική

Re: JBMO Shortlist 2019 - Συνδυαστική

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