Μαθηματική Ολυμπιάδα Αγίας Πετρούπολης 2022 (8η τάξη)

Al.Koutsouridis · #1

Μαθηματική Ολυμπιάδα Αγίας Πετρούπολης
Θέματα 8ης τάξης για την 2η φάση, 13 Φεβρουαρίου 2022.

1. 10 μαθητές συμμετείχαν σε μια ολυμπιάδα των 11 προβλημάτων. Η βαθμολογία των προβλημάτων γινόταν, μετά τον έλεγχο όλων των γραπτών, με τον εξής κανόνα: αν το πρόβλημα έχει λυθεί από ένα άτομο -4 μόρια, αν έχει λυθεί από 2 άτομα – 2 μόρια, αν από 3 ή 4 άτομα – 1 μόριο, αν περισσότερα από 4 άτομα – 0 μόρια. Να αποδείξετε ότι κάποιοι δυο μαθητές είχαν την ίδια βαθμολογία. (Ο. Ιβάνοβα)

2. Στην πλευρά

του τριγώνου ABC

δίνονται δυο σημεία

και

τέτοια, ώστε AD=CE

. Στο τμήμα

δίνεται σημείο

και στο τμήμα

σημείο

, εξάλλου

και

. Οι ημιευθείες

και

τέμνονται στο σημείο

. Να αποδείξετε, ότι το μέσο του τμήματος

βρίσκεται στην ευθεία

. (Α. Κουζνέτσοβ)

3. Να βρείτε όλα τα ζεύγη ακέραιων αριθμών x,y

, για τα οποία τα x+y

,

και

είναι τέλεια τετράγωνα. (Α. Γκολοβάνοβ)

4. Στο τραπέζι βρίσκονται 100 σταθμά διαφορετικών βαρών. Το σταθμό ονομάζεται πετυχημένο, αν το βάρος του είναι ίσο με το άθροισμα των βαρών κάποιων δυο άλλων σταθμών του τραπεζιού. Για ποιο ελάχιστο πλήθος επιτυχημένων σταθμών μπορούμε με βεβαιότητα να εγγυηθούμε, ότι τα βάρυ κάποιων δυο σταθμών διαφέρουν τουλάχιστον κατά τρεις φορές; (Σ. Μπερλόβ)

Καταληκτική αίθουσα

5. Σε μια χώρα υπάρχουν πολλές πόλεις, μεταξύ των οποίων 500 είναι μεγάλες και οι υπόλοιπες μικρές. Μερικα ζεύγη πόλεων είναι συνδεδεμένα με δρόμους έτσι, ώστε από οποιαδήποτε πόλη μπορούμε να μεταβούμε σε οποιαδήποτε άλλη. Υπάρχουν τουλάχιστον 10000 μικρές πόλεις, που συνδέονται με δρόμο τουλάχιστον με μια μεγάλη πόλη. Να αποδείξετε ότι μπορούμε να κλείσουμε μερικούς δρόμους έτσι, ώστε παρ’ όλα αυτά από οποιαδήποτε πόλη να μπορούμε να μεταβούμε σε οποιαδήποτε άλλη και να υπάρχουν πάνω από 9000 πόλεις, από τις οποίες εξέρχεται ένας δρόμος. (Δ. Καρπόβ)

6. Δίνεται ένα παραλληλόγραμμο ABCD

, στο οποίο $\angle ACB= 2 \angle CAB$ . Στην επέκταση της διαγώνιου

προς το σημείο

δίνεται σημείο

. Να αποδείξετε ότι BC+BE > DE

.

7. Δίνεται ένας πρώτος αριθμός p > 100

. Θα ονομάσουμε τον περιττό σύνθετο αριθμό n < 4p^2

παράξενο, αν για κάθε γνήσιο διαιρέτη του

τουλάχιστον ένας από τους αριθμούς q+2p

ή

επίσης να είναι φυσικός διαιρέτης του

. Να αποδείξετε ότι το πλήθος των παράξενων αριθμών δεν υπερβαίνει το $\frac{p}{3}$ . (Γνήσιος διαιρέτης ενός αριθμού

ονομάζεται κάθε διαιρέτης του διάφορος του

και

.)

Πηγή: Επίσημη σελίδα της ολυμπιάδας.

#2

Al.Koutsouridis έγραψε: ↑
Κυρ Σεπ 25, 2022 12:47 pm
Μαθηματική Ολυμπιάδα Αγίας Πετρούπολης
Θέματα 8ης τάξης για την 2η φάση, 13 Φεβρουαρίου 2022.

2. Στην πλευρά του τριγώνου δίνονται δυο σημεία και τέτοια, ώστε . Στο τμήμα δίνεται σημείο και στο τμήμα σημείο , εξάλλου και . Οι ημιευθείες και τέμνονται στο σημείο . Να αποδείξετε, ότι το μέσο του τμήματος βρίσκεται στην ευθεία . (Α. Κουζνέτσοβ)

Πηγή: Επίσημη σελίδα της ολυμπιάδας.

Η παράλληλη από το

στην

τέμνει την

στο

Προφανώς οι μοβ γωνίες είναι ίσες όπως και οι κόκκινες.

: Πετρούπολη 2022 (8)-2.png (19.01 KiB) Προβλήθηκε 1729 φορές

$\displaystyle Z\widehat AE = B\widehat DC$ κι επειδή AD=EC

θα είναι

οπότε τα τρίγωνα AZE, DBC

είναι ίσα,

άρα $\displaystyle AZ = BD = BS \Rightarrow BS|| = AZ,$ δηλαδή το AZSB

είναι παραλληλόγραμμο και

μέσο του

#3

george visvikis έγραψε: ↑
Τρί Σεπ 27, 2022 8:41 am

Al.Koutsouridis έγραψε: ↑
Κυρ Σεπ 25, 2022 12:47 pm
Μαθηματική Ολυμπιάδα Αγίας Πετρούπολης
Θέματα 8ης τάξης για την 2η φάση, 13 Φεβρουαρίου 2022.

2. Στην πλευρά του τριγώνου δίνονται δυο σημεία και τέτοια, ώστε . Στο τμήμα δίνεται σημείο και στο τμήμα σημείο , εξάλλου και . Οι ημιευθείες και τέμνονται στο σημείο . Να αποδείξετε, ότι το μέσο του τμήματος βρίσκεται στην ευθεία . (Α. Κουζνέτσοβ)

Πηγή: Επίσημη σελίδα της ολυμπιάδας.
Η παράλληλη από το στην τέμνει την στο Προφανώς οι μοβ γωνίες είναι ίσες όπως και οι κόκκινες. Πετρούπολη 2022 (8)-2.png
$\displaystyle Z\widehat AE = B\widehat DC$ κι επειδή θα είναι οπότε τα τρίγωνα είναι ίσα,

άρα $\displaystyle AZ = BD = BS \Rightarrow BS|| = AZ,$ δηλαδή το είναι παραλληλόγραμμο και μέσο του

Ωραία και χωρίς Μενέλαο .

Ορέστης Λιγνός · #4

Al.Koutsouridis έγραψε: ↑
Κυρ Σεπ 25, 2022 12:47 pm
Μαθηματική Ολυμπιάδα Αγίας Πετρούπολης
Θέματα 8ης τάξης για την 2η φάση, 13 Φεβρουαρίου 2022.

3. Να βρείτε όλα τα ζεύγη ακέραιων αριθμών , για τα οποία τα , και είναι τέλεια τετράγωνα. (Α. Γκολοβάνοβ)

Πηγή: Επίσημη σελίδα της ολυμπιάδας.

Έστω

,

και

. Εύκολα προκύπτει ότι 7a^2=2b^2+c^2

(πράγματι, 7a^2=7x+7y=2(2x+3y)+(3x+y)=2b^2+c^2

).

Δουλεύοντας $\pmod 7$ , είναι $2b^2+c^2 \equiv 0 \pmod 7$ , οπότε εύκολα προκύπτει ότι $7 \mid b,c$ (αν $7 \nmid b,c$ και

τέτοιο ώστε $c \equiv bx \pmod 7$ , τότε $7 \mid 2b^2+b^2x^2=b^2(x^2+2)$ , άρα $x^2 \equiv 5 \pmod 7$ , άτοπο καθώς το

δεν είναι τετραγωνικό υπόλοιπο $\pmod 7$ ).

Αν b=7b'

,

τότε

, άρα $7 \mid a$ , οπότε αν a=7a'

τότε

, και συνεχίζοντας όμοια (άπειρη κάθοδος) προκύπτει ότι πρέπει a=b=c=0

, οπότε τελικά και x=y=z=0

.

Ορέστης Λιγνός · #5

Al.Koutsouridis έγραψε: ↑
Κυρ Σεπ 25, 2022 12:47 pm
Μαθηματική Ολυμπιάδα Αγίας Πετρούπολης
Θέματα 8ης τάξης για την 2η φάση, 13 Φεβρουαρίου 2022.

6. Δίνεται ένα παραλληλόγραμμο , στο οποίο $\angle ACB= 2 \angle CAB$ . Στην επέκταση της διαγώνιου προς το σημείο δίνεται σημείο . Να αποδείξετε ότι .

Έστω

το συμμετρικό του

ως προς την

. Τότε, είναι $\angle AXC=\angle ABC=\angle ADC,$ άρα το τετράπλευρο ADXC

είναι εγγράψιμο, και $\angle ACX=\angle ACB=\angle CAD,$ άρα είναι ισοσκελές τραπέζιο.

Επίσης, ΄

$\angle DAX=\angle DCX=\angle ACX-\angle ACD=\angle DAC-\angle ACD=\angle ACD=\angle DXA,$

συνεπώς DX=DA=BC

. Τελικά, λόγω της τριγωνικής ανισότητας,

BC+BE=DX+XE>DE,

όπως θέλαμε.

Ορέστης Λιγνός · #6

Al.Koutsouridis έγραψε: ↑
Κυρ Σεπ 25, 2022 12:47 pm
Μαθηματική Ολυμπιάδα Αγίας Πετρούπολης
Θέματα 8ης τάξης για την 2η φάση, 13 Φεβρουαρίου 2022.

7. Δίνεται ένας πρώτος αριθμός . Θα ονομάσουμε τον περιττό σύνθετο αριθμό παράξενο, αν για κάθε γνήσιο διαιρέτη του τουλάχιστον ένας από τους αριθμούς ή επίσης να είναι φυσικός διαιρέτης του . Να αποδείξετε ότι το πλήθος των παράξενων αριθμών δεν υπερβαίνει το $\frac{p}{3}$ . (Γνήσιος διαιρέτης ενός αριθμού ονομάζεται κάθε διαιρέτης του διάφορος του και .)

Πηγή: Επίσημη σελίδα της ολυμπιάδας.

Έστω

ο μέγιστος γνήσιος διαιρέτης του

. Αν $a \leq 2p$ , τότε πρέπει $a+2p \mid n$ , άτοπο αφού a+2p>a

. Άρα

και $a-2p \mid n$ .

Ισχυρισμός 1: Ο

γράφεται στη μορφή n=a(a+2p)b

με

θετικό ακέραιο. Επίσης, 2p<a<4p

.
Απόδειξη: Αν $p \mid a$ , τότε $p \mid a \mid n$ , άρα $3p=p+2p \mid n$ , οπότε $3 \mid n$ , συνεπώς και $3+2p \mid n$ . Αφού όμως $\gcd(3p,3+2p)=1$ , είναι $3p(3+2p) \mid n$ , συνεπώς
4p^2>n>3p(3+2p)>6p^2,

άτοπο. Άρα, $p \nmid a$ , που δίνει ότι $\gcd(a,a-2p)=1$ , και άρα $a(a-2p) \mid n$ , που δίνει το ζητούμενο. Αν τώρα ήταν $a \geq 4p,$ τότε

$n =a(a-2p)b \geq 4p \cdot 2p>4p^2,$

άτοπο $\blacksquare$

Τώρα διακρίνουμε κάποιες περιπτώσεις.

Περίπτωση 1: Ο

δεν είναι πρώτος. Προφανώς a>1

. Έστω τότε

ο μέγιστος γνήσιος διαιρέτης του

. Είναι,
$q \leq \dfrac{a}{2}<2p,$

άρα $q+2p \mid n$ , οπότε αφού $b \mid n$ , είναι ${\rm lcm}(q+2p,b) \mid n$ , οπότε είτε ${\rm lcm}(q+2p,b)+2p \mid n$ , είτε ${\rm lcm}(q+2p,b)-2p \mid n$ . Αν ισχύει η πρώτη διαιρετότητα, τότε αφού

ο μέγιστος διαιρέτης του

, πρέπει

$a \geq {\rm lcm}(q+2p,b)+2p \geq (q+2p)+2p >4p,$

άτοπο από τον Ισχυρισμό 1. Άρα ισχύει η δεύτερη, οπότε όμοια

$a \geq {\rm lcm}(q+2p,b)-2p$

Αν ${\rm lcm}(q+2p,b) \geq 3(q+2p)$ , τότε $a \geq 3(q+2p)-2p>4p,$ άτοπο. Αν ${\rm lcm}(q+2p,b)=2(q+2p)$ , τότε $\gcd(q+2p,b)=\dfrac{(q+2p)b}{{\rm lcm}(q+2p,b)}=\dfrac{b}{2},$ άρα $2 \mid b \mid n$ , άτοπο αφού

περιττός.

Συνεπώς, ${\rm lcm}(q+2p,b) =q+2p$ , και άρα $q+2p \mid b$ , οπότε

$n=a(a-2p)b \geq ab >2p(q+2p)>4p^2,$

άτοπο.

Περίπτωση 2: Ο a-2p

δεν είναι πρώτος και είναι

. Όμοια με πριν, ακολουθούμε την ίδια διαδικασία και προκύπτει άτοπο.

Περίπτωση 3: Οι a,a-2p

είναι και οι δύο πρώτοι ή

. Τότε, αν a-2p=1

, τότε

, με

πρώτο, οπότε b>1

γιατί αν

ο

θα ήταν πρώτος, άτοπο. Αν λοιπόν

ο μέγιστος πρώτος που διαιρεί το

, τότε θα είναι $q(2p+1) \mid n$ , άρα

$q(2p+1)-2p \mid n$ , γιατί διαφορετικά πρέπει $q(2p+1)+2p \mid n$ , οπότε $a \geq q(2p+1)+2p >4p,$ άτοπο. Αφού όμως $\gcd(q(2p+1)-2p,2p+1)=1,$ προκύπτει ότι $q(2p+1)-2p \mid b$ , άρα

$q(2p+1)-2p \leq q,$ που ισοδυναμεί με $q \leq 1$ , άτοπο.

Συνεπώς a-2p>1

, άρα είναι πρώτος.

Ισχυρισμός 2: Είναι b=1

.
Απόδειξη: Πράγματι, αν b>1

, υπάρχει $q \mid b$ , και αν $q \geq 2p$ τότε

$n=a(a-2p)b \geq ab >2pq \geq 4p^2,$

άτοπο. Άρα q <2p

οπότε $q+2p \mid n$ , και συνεπώς $q+2p \mid a(a-2p)b$ . Όμως είναι $\gcd(q+2p,b)=\gcq(q,p)=1,$ και άρα $q+2p \in \{a-2p,a,a(a-2p) \}$

Αν q+2p=a-2p

τότε

άτοπο, άρα $q+2p \in \{a,a(a-2p) \}$ .

Αν q=a-2p

τότε

, οπότε

και άρα $a(a-2p)^2 \pm 2p \mid n$ , οπότε σε κάθε περίπτωση

$a(a-2p)^2-2p \leq a$ , άρα αν a=2p+u

, τότε $(2p+u)u^2 \leq 4p+u$ , συνεπώς αν $u \geq 2$ προκύπτει ότι

$4p+u \geq (2p+u)u^2=2u^2p+u^3>4p+u,$

άτοπο. Άρα u=1

και

, οπότε

άτοπο.

Αν πάλι q=a(a-2p)

, τότε

, οπότε

και άρα $a^2(a-2p)^2 \pm 2p \mid n$ , οπότε σε κάθε περίπτωση

$a^2(a-2p)^2 -2p \leq a$ , άρα αν a=2p+u

, τότε

$4p+u \geq (2p+u)^2u^2 \geq (4p^2+u^2)u^2 >4p+u,$

άτοπο. $\blacksquare$

Τελικά, πρέπει n=a(a-2p)

με

και

πρώτους.

Αν $p \equiv 1 \pmod 3$ , τότε εύκολα πρέπει $a \equiv 1 \pmod 3$ , άρα $a-2p \equiv 2 \pmod 3$ , οπότε προκύπτει ότι το πλήθος των παράξενους αριθμών είναι μικρότερος από το πλήθος των πρώτων στο [1,2p]

που είναι $1 \pmod 3$ . Όμως, σε κάθε έξι διαδοχικούς αριθμούς

2k,2k+1,2k+2,2k+3,2k+4,2k+5

ή

,

το πολύ ένας μπορεί να είναι πρώτος και $1 \pmod 3$ (οι 2k,2k+2,2k+4

στην πρώτη εξάδα είναι άρτιοι, και οι 2k+1,2k+3,2k+5

είναι αναδιάταξη των $0,1,2 \pmod 3$ . Όμοια στη δεύτερη εξάδα).

Άρα, αφού έχουμε <2p/6=p/3

εξάδες διαδοχικών αριθμών, έχουμε το πολύ p/3

παράξενους αριθμούς, όπως θέλαμε.

Ορέστης Λιγνός · #7

Al.Koutsouridis έγραψε: ↑
Κυρ Σεπ 25, 2022 12:47 pm
Μαθηματική Ολυμπιάδα Αγίας Πετρούπολης
Θέματα 8ης τάξης για την 2η φάση, 13 Φεβρουαρίου 2022.

4. Στο τραπέζι βρίσκονται 100 σταθμά διαφορετικών βαρών. Το σταθμό ονομάζεται πετυχημένο, αν το βάρος του είναι ίσο με το άθροισμα των βαρών κάποιων δυο άλλων σταθμών του τραπεζιού. Για ποιο ελάχιστο πλήθος επιτυχημένων σταθμών μπορούμε με βεβαιότητα να εγγυηθούμε, ότι τα βάρυ κάποιων δυο σταθμών διαφέρουν τουλάχιστον κατά τρεις φορές; (Σ. Μπερλόβ)

Θα λύσουμε το αντίστροφο πρόβλημα, δηλαδή ότι "αν για τα βάρη $a_1<a_2<\ldots<a_{100}$ των σταθμών ισχύει ότι $a_{100} <3a_1$ , τότε ποιος είναι ο μέγιστος αριθμός επιτυχημένων σταθμών;"

Η απάντηση είναι

σταθμά. Έστω $x_{i_1}<x_{i_2}<\ldots<x_{i_r}$ τα επιτυχημένα σταθμά. Τότε, ονομάζουμε κάθε σταθμό με βάρος $\geq x_{i_1}$ μεγάλο, και μικρό αν έχει βάρος $<x_{i_1}$ . Έχουμε τον ακόλουθο Ισχυρισμό.

Ισχυρισμός: Αν $x_{i_j}$ ένα επιτυχημένο σταθμό και $x_{i_j}=x_k+x_\ell$ , τότε τα $x_k,x_\ell$ είναι και τα δύο μικρά.
Απόδειξη: Αν το x_k

ήταν μεγάλο, τότε

$3x_1>x_{100} \geq x_{i_j}=x_k+x_\ell \geq x_{i_j}+x_1=x_m+x_n+x_1 \geq 3x_1,$

άτοπο. Άρα έχουμε το ζητούμενο $\blacksquare$

Από τον Ισχυρισμό έχουμε ότι για κάθε $j \in \{1,2, \ldots, r\}$ υπάρχουν $k,\ell<i_1$ με $x_{i_j}=x_k+x_\ell$ .

Άρα, πρέπει $r \leq \dfrac{(i_1-1)(i_1-2)}{2}$ , αφού τα μη διατεταγμένα ζεύγη $(k,\ell)$ είναι διαφορετικά για κάθε

.

Επίσης, $100 \geq i_r \geq i_1+(r-1),$ άρα $i_1 \leq 101-r$ , συνεπώς

$r \leq \dfrac{(i_1-1)(i_1-2)}{2} \leq \dfrac{(100-r)(99-r)}{2},$

που δίνει ότι $r \leq 86$ . Αν r=86

, εύκολα προκύπτει ότι πρέπει i_1=15

, άρα όλα τα σταθμά $a_{15},\ldots,a_{100}$ είναι επιτυχημένα, και τα υπόλοιπα δεν είναι.

Πρέπει να επιλέξουμε κατάλληλα τα βάρη $a_1<a_2<\ldots<a_{14}$ . Θα επιλέξουμε τα βάρη αυτά ώστε να έχουν τις εξής ιδιότητες:

$\bullet$ $a_{14} <\dfrac{3a_1}{2}$ και
$\bullet$ κάθε δύο αθροίσματα της μορφής x_j+x_k

είναι διαφορετικά.

Αυτές οι δύο συνθήκες εξασφαλίζουν ότι $a_{15} \geq a_1+a_2 >2a_1>\dfrac{3a_1}{2}>a_{14}$ , καθώς και ότι $a_{100} \leq a_{15}+a_{14}<2a_{15}<3a_1$ , ενώ τέλος εξασφαλίζουν ότι μπορούμε να επιλέξουμε από τα $14 \cdot 13/2=91$ διαφορετικά αθροίσματα της μορφής x_j+x_k

τα

διαφορετικά που θέλουμε.

Για να γίνει αυτή η επιλογή, απλώς προχωράμε επαγωγικά. Δηλαδή, αν έχουμε επιλέξει τα $a_1,\ldots,a_j$ όπως θέλουμε, επιλέγουμε τον $a_{j+1}$ όσο μικρό θέλουμε (αρκεί να είναι >a_j

), με την ιδιότητα τα αθροίσματα $a_{j+1}+a_t$ με $t \leq j$ να είναι διαφορετικά από τα ήδη υπάρχοντα αθροίσματα. Είναι σαφές ότι μπορούμε να κάνουμε την επιλογή με αυτόν τον τρόπο.

Συνεπώς, η απάντηση στο αρχικό πρόβλημα είναι

βάρη (αν έχουμε το πολύ

επιτυχημένα έχουμε δώσει αντιπαράδειγμα, αν έχουμε πάνω από

επιτυχημένα τότε προκύπτει άτοπο με βάση τα πιο πάνω).

#8

Al.Koutsouridis έγραψε: ↑
Κυρ Σεπ 25, 2022 12:47 pm
5. Σε μια χώρα υπάρχουν πολλές πόλεις, μεταξύ των οποίων 500 είναι μεγάλες και οι υπόλοιπες μικρές. Μερικα ζεύγη πόλεων είναι συνδεδεμένα με δρόμους έτσι, ώστε από οποιαδήποτε πόλη μπορούμε να μεταβούμε σε οποιαδήποτε άλλη. Υπάρχουν τουλάχιστον 10000 μικρές πόλεις, που συνδέονται με δρόμο τουλάχιστον με μια μεγάλη πόλη. Να αποδείξετε ότι μπορούμε να κλείσουμε μερικούς δρόμους έτσι, ώστε παρ’ όλα αυτά από οποιαδήποτε πόλη να μπορούμε να μεταβούμε σε οποιαδήποτε άλλη και να υπάρχουν πάνω από 9000 πόλεις, από τις οποίες εξέρχεται ένας δρόμος. (Δ. Καρπόβ)

Η άσκηση μας δίνει ένα συνεκτικό γράφημα

. Οι κορυφές του χωρίζονται σε δύο υποσύνολα

και

με το

να έχει

κορυφές και το

τουλάχιστον 10000

κορυφές ώστε κάθε κορυφή του

να είναι γειτονική με τουλάχιστον μία κορυφή του

. Θέλουμε να βρούμε ένα συνεκτικό υπογράφημα

με τις ίδιες κορυφές ώστε τουλάχιστον 9000

κορυφές του να έχουν βαθμό ακριβώς

.

Κατασκευάζουμε το

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

ή και τα δύο άκρα της να βρίσκονται στο σύνολο

. Αν αυτό δεν είναι δυνατό τότε επιλέγουμε οποιαδήποτε ακμή του κύκλου για να αφαιρεθεί.

Στο τέλος θα μας μείνει ένα δέντρο

. Από τα δεδομένα και την κατασκευή του

, κάυε κορυφή του

θα εξακολουθεί να είναι γειτονική με τουλάχιστον μία κορυφή του

. Αν περιορίσουμε το

στο σύνολο

θα έχουμε μια ένωση από δέντρα, έστω τα $T_1,\ldots,T_k$ . Αν περιορίσουμε το

στο σύνολο

θα έχουμε μια ένωση από δέντρα, έστω τα $S_1,\ldots,S_{\ell}$ .

Κατασκευάζουμε τώρα ένα νέο γράφημα

με κορυφές τα δέντρα $T_1,\ldots,T_k,S_1,\ldots,S_{\ell}$ όπου συνδέουμε τα T_i

με

αν και μόνο αν έχουν δυο γειτονικές κορυφές. Είναι άμεσο ότι το

πρέπει να είναι δέντρο και άρα να έχει ακριβώς $k+\ell-1 \leqslant 499 + \ell$ ακμές. Παρατηρούμε ότι αν έχουμε ακμή μεταξύ των T_i

και

στο

, τότε αυτή αντιστοιχεί σε ακριβώς μία ακμή στο

αφού αν είχαμε περισσότερες θα δημιουργείτο κύκλος.

Άρα στο

έχουμε το πολύ $499+\ell$ ακμές μεταξύ κορυφών του

και κορυφών του

. Άρα έχουμε το πολύ 499

δέντρα στο

με δύο ή περισσότερες ακμές από αυτά στο

. Συνεπώς έχουμε τουλάχιστον $\ell-499$ δέντρα στο

με ακριβώς μία ακμή από αυτά στο

. Κάθε τέτοιο δέντρο πρέπει να είναι μεμονωμένη κορυφή. (Αφού κάθε κορυφή του δέντρο έχει γείτονα στο

.).

Όμως, αφού έχουμε τουλάχιστον 10000

κορυφές στο

τότε $499 + \ell \geqslant 10000$ οπότε $\ell - 499 \geqslant 10000 - 2\cdot 499 = 9002$ . Δηλαδή στο

έχουμε τουλάχιστον 9002

κορυφές βαθμού

όπως θέλαμε να δείξουμε.

Άσκηση: Δώστε παράδειγμα για την οποία το 9002

είναι βέλτιστο.

#9

Al.Koutsouridis έγραψε: ↑
Κυρ Σεπ 25, 2022 12:47 pm

1. 10 μαθητές συμμετείχαν σε μια ολυμπιάδα των 11 προβλημάτων. Η βαθμολογία των προβλημάτων γινόταν, μετά τον έλεγχο όλων των γραπτών, με τον εξής κανόνα: αν το πρόβλημα έχει λυθεί από ένα άτομο -4 μόρια, αν έχει λυθεί από 2 άτομα – 2 μόρια, αν από 3 ή 4 άτομα – 1 μόριο, αν περισσότερα από 4 άτομα – 0 μόρια. Να αποδείξετε ότι κάποιοι δυο μαθητές είχαν την ίδια βαθμολογία. (Ο. Ιβάνοβα)

Αφήσαμε τελευταίο το πιο εύκολο. Έστω προς άτοπο ότι όλοι οι μαθητές είχαν διαφορετική βαθμολογία. Τότε το άθροισμα των βαθμολογιών θα ήταν τουλάχιστον $0+1+2+\cdots+9 = 45$ . Από την άλλη κάθε πρόβλημα δίνει συνολικά το πολύ

βαθμούς σε όσους το έλυσαν. Άρα το άθροισμα των βαθμολογιών είναι το πολύ $4 \cdot 11 = 44$ . Αυτό όμως είναι άτοπο.

Μαθηματική Ολυμπιάδα Αγίας Πετρούπολης 2022 (8η τάξη)

Μαθηματική Ολυμπιάδα Αγίας Πετρούπολης 2022 (8η τάξη)

Re: Μαθηματική Ολυμπιάδα Αγίας Πετρούπολης 2022 (8η τάξη)

Re: Μαθηματική Ολυμπιάδα Αγίας Πετρούπολης 2022 (8η τάξη)

Re: Μαθηματική Ολυμπιάδα Αγίας Πετρούπολης 2022 (8η τάξη)

Re: Μαθηματική Ολυμπιάδα Αγίας Πετρούπολης 2022 (8η τάξη)

Re: Μαθηματική Ολυμπιάδα Αγίας Πετρούπολης 2022 (8η τάξη)

Re: Μαθηματική Ολυμπιάδα Αγίας Πετρούπολης 2022 (8η τάξη)

Re: Μαθηματική Ολυμπιάδα Αγίας Πετρούπολης 2022 (8η τάξη)

Re: Μαθηματική Ολυμπιάδα Αγίας Πετρούπολης 2022 (8η τάξη)

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