IMO 2014 (Shortlisted Problems)

#1

Κάνω μία αντίστοιχη κίνηση με αυτή του Σωτήρη για τις JBMO. Εδώ θα βάζω με τη σειρά τα A1,C1,G1,N1 κοκ γιατί παρατηρείται μεγάλη διαφορά στη δυσκολία:
Τα A1, G1, G5, C3, C5, N3 μπήκαν στο διαγωνισμό και δεν θα τα προτείνω εδώ.

Algebra 2

Θεωρούμε τη συνάρτηση $f:(0,1)\rightarrow (0,1)$ με τύπο:
$f(x)= \begin{cases} x+\frac{1}{2} &\mbox{if } x<\frac{1}{2} \\ x^2 & \mbox{if } x\geq\frac{1}{2}. \end{cases}$

Έστω επίσης 0<a<b<1

δύο πραγματικοί αριθμοί. Ορίζουμε τις ακολουθίες a_n,b_n

ως εξής: $a_0=a,\ b_0=b$ και $a_n=f(a_{n-1}),\ b_n=f(b_{n-1}).$
Να αποδειχθεί ότι υπάρχει θετικός ακέραιος

τέτοιος ώστε
$(a_n-a_{n-1})(b_n-b_{n-1})<0.$

#2

Συνεχίζω, ας μην απαντήθηκε το πρώτο:

Combinatorics 1
Δίνονται

σημεία στο εσωτερικό ενός ορθογωνίου

έτσι ώστε να μην υπάρχουν δύο σε ευθεία παράλληλη σε πλευρά του

Θέλουμε να διαμερίσουμε το

σε μικρότερα ορθογώνια με πλευρές παράλληλες σε αυτές του

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

σε τουλάχιστον n+1

μικρότερα ορθογώνια.

gavrilos · #3

smar έγραψε:Συνεχίζω, ας μην απαντήθηκε το πρώτο:

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

Μπορούμε να σκεφτούμε ως εξής:

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

Έστω $\displaystyle{f(n)}$ ο ελάχιστος αριθμός ορθογωνίων σε μια αποδεκτή διαμέριση για $\displaystyle{n}$ σημεία.Προφανώς $\displaystyle{f(1)=2}$ .

Θα δείξουμε ότι η $\displaystyle{f}$ είναι γνησίως αύξουσα.Έστω $\displaystyle{f(m)\geq f(n)}$ και $\displaystyle{m<n}$ .

Τότε από τη διαμέριση των $\displaystyle{n}$ σημείων με αριθμό ορθογωνίων $\displaystyle{f(n)}$ αφαιρούμε $\displaystyle{n-m}$ σημεία και μαζί τα τμήματα που περνούν από αυτά τα σημεία.

Αν κάποια ορθογώνια τώρα έχουν μείνει "ανοικτά" προεκτείνουμε τις "ανοικτές" πλευρές τους μέχρι την πρώτη κάθετη που θα συναντήσουμε.

Έτσι δε δημιουργούνται νέα ορθογώνια.Έχουμε μείνει με μια αποδεκτή διαμέριση $\displaystyle{m}$ σημείων και έστω πως το πλήθος ορθογωνίων είναι $\displaystyle{A}$ .

Αφαιρώντας τμήματα σίγουρα θα μειώθηκε ο αριθμός των συνολικών ορθογωνίων άρα $\displaystyle{A<f(n)\leq f(m)}$ που είναι άτοπο από τον ορισμό της $\displaystyle{f}$ .

Άρα για οποιουσδήποτε θετικούς ακεραίους $\displaystyle{m,n}$ με $\displaystyle{m<n}$ ισχύει $\displaystyle{f(m)<f(n)}$ άρα η $\displaystyle{f}$ είναι γνησίως αύξουσα.

Επομένως $\displaystyle{f(n)-f(n-1)\geq 1}$ .Αθροίζοντας από $\displaystyle{1}$ ως $\displaystyle{n}$ παίρνουμε $\displaystyle{f(n)-f(1)\geq n-1\Leftrightarrow f(n)\geq n+1}$ που είναι το ζητούμενο.

Εύκολα μπορούμε να βρούμε παράδειγμα διαμέρισης με ακριβώς $\displaystyle{n+1}$ μικρότερα ορθογώνια.

Ενημερώστε με αν χρειάζεται κάπου επιπλέον δικαιολόγηση.

#4

smar έγραψε:Συνεχίζω, ας μην απαντήθηκε το πρώτο:

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

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

, για να το επιτύχουμε αυτό πρέπει να φέρουμε τουλάχιστον

ευθύγραμμα τμήματα.

Κοιτάζω άκρα των ευθυγράμμων τμημάτων. Αν το άκρο ανήκει σε πλευρά του

τότε σχηματίζει εκεί δύο ορθές γωνίες. Αν όχι, τότε πρέπει απαραίτητα να ανήκει και σε ένα άλλο ευθύγραμμο τμήμα. Με αυτό είτε θα σχηματίζει δύο ορθές γωνίες από την μία πλευρά (και μία γωνία 180 μοιρών από την άλλη) είτε θα σχηματίζει μία ορθή γωνία και μία γωνία 270 μοιρών. Το τελευταίο όμως είναι αδύνατον αφού τότε δεν μπορούμε να έχουμε διαμερισμό σε ορθογώνια.

Άρα σε κάθε περίπτωση, κάθε άκρο μας δίνει δύο ορθές γωνίες. Από την άλλη, κάθε μια από αυτές τις ορθές γωνίες αντιστοιχεί σε ακριβώς ένα άκρο ευθυγράμμου τμήματος. (Αφού πάλι δεν μπορούμε να έχουμε την περίπτωση που δυο άκρα ευθυγράμμων τμημάτων ταυτίζονται.)

Άρα έχουμε δημιουργήσει τουλάχιστον

ορθές γωνίες που μαζί με τις αρχικές μας δίνουν τουλάχιστον 4n+4 = 4(n+1)

ορθές γωνίες. Άρα έχουμε και τουλάχιστον n+1

ορθογώνια.

#5

Combinatorics 2
Έχουμε 2^m

φύλλα χαρτιού που έχουν γραμμένο πάνω τους τον αριθμό 1. Εκτελούμε την παρακάτω διαδικασία:
Σε κάθε βήμα διαλέγουμε δύο διαφορετικά φύλλα. Αν οι αριθμοί στα δύο φύλλα είναι a,b

τότε τους σβήνουμε και γράφουμε και στα δύο χαρτιά τον αριθμό a+b.

Να αποδειχθεί ότι μετά από $m2^{m-1}$ βήματα το άθροισμα όλων των αριθμών σε όλα τα φύλλα είναι τουλάχιστον 4^m.

Geometry 2
Έστω ABC

ένα τρίγωνο και AK,BL,CM

τρεις σεβιανές του. Να αποδειχθεί ότι μπορούμε να διαλέξουμε δύο τρίγωνα από τα ALM,BMK,CKL

των οποίων το άθροισμα των ακτίνων των εγγεγραμμένων κύκλων να είναι τουλάχιστον όσο η ακτίνα του εγγεγραμμένου κύκλου του τριγώνου ABC.

#6

Number theory 1
Έστω $n\geq 2$ ένας ακέραιος και $A_n=\{2^n-2^k\ |k\in\mathbb{Z},\ 0\leq k<n\}.$

Να προσδιοριστεί ο μεγαλύτερος θετικός ακέραιος που δεν μπορεί να γραφεί σαν άθροισμα ενός ή περισσότερων (όχι αναγκαστικά διαφορετικών) στοιχείων του A_n.

Number theory 2
Να προσδιορίσετε όλα τα ζεύγη θετικών ακεραίων που είναι τέτοια ώστε:
$\sqrt[3]{7x^2-13xy+7y^2}=|x-y|+1.$

Αρχιμήδης 6 · #7

smar έγραψε:
Number theory 2
Να προσδιορίσετε όλα τα ζεύγη θετικών ακεραίων που είναι τέτοια ώστε:
$\sqrt[3]{7x^2-13xy+7y^2}=|x-y|+1.$

ΕΜΦΑΝΙΣΗ ΚΕΙΜΕΝΟΥ

#8

smar έγραψε:Combinatorics 2
Έχουμε φύλλα χαρτιού που έχουν γραμμένο πάνω τους τον αριθμό 1. Εκτελούμε την παρακάτω διαδικασία:
Σε κάθε βήμα διαλέγουμε δύο διαφορετικά φύλλα. Αν οι αριθμοί στα δύο φύλλα είναι τότε τους σβήνουμε και γράφουμε και στα δύο χαρτιά τον αριθμό
Να αποδειχθεί ότι μετά από $m2^{m-1}$ βήματα το άθροισμα όλων των αριθμών σε όλα τα φύλλα είναι τουλάχιστον

Την βρήκα λίγο δύσκολη για 2. Δεν ξέρω αν υπάρχει κάτι πιο απλό από το πιο κάτω.

Λήμμα: Έστω ότι έχουμε 2^m

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

βήματα. Έστω

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

με πιθανώς μια άλλη διαδικασία

βημάτων όπου στο πρώτο βήμα αντί να κάνω την συνήθη αλλαγή όπου τα φύλλα a,b

γίνονται και τα δύο a+b

, κάνω στην θέση του την αλλαγή όπου διπλασιάζω τους αριθμούς των φύλλων.

Πριν να αποδειχθεί το λήμμα ας δούμε πως μας δίνει σχεδόν άμεσα το ζητούμενο.

Εφαρμόζοντας το λήμμα επαγωγικά μπορώ να υποθέσω ότι σε κάθε βήμα εφαρμόζω διπλασιασμό των φύλλων. Αφού σε $m2^{m-1}$ βήματα θα κάνω m2^m

πολλαπλασιασμούς στο τέλος θα έχω στα φύλλα τους αριθμούς $2^{a_1},\ldots,2^{a_{2^m}}$ όπου $a_1+\cdots +a_{2^m} = m2^m$ .

Από την κυρτότητα της 2^x

το άθροισμα ελαχιστοποιείται όταν $a_1 = \cdots =a_{2^m} = m$ . Τότε το άθροισμα ισούται με 4^m

.

Απόδειξη λήμματος: Έστω ότι έχω τους αριθμούς $x_1,x_2,\ldots,x_{2^m}$ και χωρίς βλάβη της γενικότητας στο πρώτο βήμα της διαδικασίας που μου δίνει άθροισμα

αλλάζω τα χαρτιά 1 και 2. Έστω $y_1,y_2,y_3,\ldots,y_{2^m}$ οι αριθμοί στα χαρτιά αμέσως μετά το πρώτο βήμα. [Οπότε είναι y_1=y_2=x_1+x_2

και

για $i \geqslant 3$ .]

Εφαρμόζοντας την υπόλοιπη διαδικασία στους αριθμούς $y_1,\ldots,y_{2^m}$ μέχρι τέλους θα καταλήξω σε ένα άθροισμα το οποίο είναι γραμμικό στα $y_1,y_2,\ldots,y_{2^m}$ . Έστω το άθροισμα ισούται με $k_1y_1 + \cdots + k_{2^m}y_{2^m}$ . Έστω χωρίς βλάβη της γενικότητας ότι $k_1 \leqskant k_2$ .

Περίπτωση 1: Αν $x_1 \geqslant x_2$ τότε αν αντί y_1=y_2 = x_1+x_2

πάρω

και

τότε το άθροισμα μειώνεται κατά $(k_2-k_1)(x_1-x_2) \geqslant 0$ .

Περίπτωση 2: Αν $x_1 \geqslant x_2$ τότε αν αντί y_1=y_2 = x_1+x_2

πάλι παίρνω y_1 = 2x_1

και

. Μόνο που στα υπόλοιπα βήματα εναλλάσσω τις εμφανίσεις των χαρτιών 1 και 2. (Π.χ. εκεί που οι οδηγίες λένε πάρα τα χαρτιά 1 και 5 εγώ παίρνω τα χαρτιά 2 και 5 κ.τ.λ.) Αυτό έχει σαν αποτέλεσμα το τελικό άθροισμα να ισούται με $k_2y_1 + k_1y_2 + k_3y_3 + \cdots + k_{2^m}y_{2^m}$ . Οπότε πάλι το άθροισμα δεν αυξάνεται.

Επομένως το λήμμα έχει αποδειχθεί.

#9

Ολοκληρώνω τη συλλογή της άλγεβρας.
Algebra 3
Για μία ακολουθία x_1,...,x_n

πραγματικών αριθμών ορίζουμε τιμή την ποσότητα $\displaystyle{\max_{1\leq i\leq n}|x_1+\ldots+x_i|.}$

Δοθέντων

πραγματικών αριθμών, ο Γιάννης και ο Γιώργος θέλουν να τους βάλουν σε μία σειρά ώστε η ακολουθία που θα προκύψει να έχει χαμηλή τιμή.

Ο Γιάννης κοιτάζει έναν έναν όλους τους πιθανούς τρόπους μετάθεσης και βρίσκει μία ελάχιστη τιμή

O Γιώργος, κάνει τη διαδικασία σε βήματα. Πρώτα διαλέγει τον x_1

έτσι ώστε ο |x_1|

να είναι ο μικρότερος. Από τους υπόλοιπους διαλέγει τον x_2

έτσι ώστε
ο |x_1+x_2|

να είναι ο μικρότερος, και λοιπά. Αν σε κάποιο βήμα έχει περισσότερες από μία επιλογές για τον x_i

διαλέγει έναν στην τύχη. Τελικά καταλήγει σε μία ακολουθία με τιμή

Να βρεθεί η μικρότερη σταθερά

έτσι ώστε για κάθε

και για κάθε συλλογή

αριθμών να ισχύει: $G\leq cD.$

Algebra 4
Να προσδιορίσετε όλες τις συναρτήσεις $f:\mathbb{Z}\rightarrow\mathbb{Z}$ που ικανοποιούν την εξίσωση:
f(f(m)+n)+f(m)=f(n)+f(3m)+2014.

Algebra 5
Να προσδιορίσετε όλα τα πολυώνυμα P(x)

με πραγματικούς συντελεστές που ικανοποιούν την ακόλουθη συνθήκη:
Για κάθε $x,y\in\mathbb{R}$ ισχύει ότι $|y^2-P(x)|\leq 2|x|$ αν και μόνο αν $|x^2-P(y)|\leq 2|y|.$

Algebra 6
Να βρεθούν όλες οι συναρτήσεις $f:\mathbb{Z}\rightarrow\mathbb{Z}$ που είναι τέτοιες ώστε
n^2+4f(n)=(f(f(n)))^2.

#10

smar έγραψε:Number theory 1
Έστω $n\geq 2$ ένας ακέραιος και $A_n=\{2^n-2^k\ |k\in\mathbb{Z},\ 0\leq k<n\}.$

Να προσδιοριστεί ο μεγαλύτερος θετικός ακέραιος που δεν μπορεί να γραφεί σαν άθροισμα ενός ή περισσότερων (όχι αναγκαστικά διαφορετικών) στοιχείων του

Κυρίως άλγεβρα παρά αριθμοθεωρία το βρήκα.

Ο μέγιστος αριθμός που δεν μπορούμε να γράψουμε είναι ο (n-2)2^n + 1

. Αυτό είναι απλό για n=2

. Για την απόδειξη θα χρησιμεύσει σε διάφορα βήματα το γεγονός ότι $\displaystyle{ A_{n+1} = 2A_n \cup \{2^{n+1}-1\}}$ όπου με

συμβολίζω το σύνολο $\{2a:a\in A\}$ .

Ισχυρισμός 1: Μπορώ να γράψω κάθε αριθμό μεγαλύτερο ή ίσο με τον (n-2)2^n+2

.

Απόδειξη: Επαγωγικά. Για n=2

είναι απλό. Αν ισχύει για n=k

, από την επαγωγική υπόθεση μπορώ να γράψω κάθε άρτιο μεγαλύτερο ή ίσο του 2((k-2)2^k+2)

. (Εδώ χρησιμοποιώ το $A_{k+1} = 2A_k \cup \{2^{k+1}-1\}.)$ Άρα μπορώ να γράψω και κάθε άρτιο μεγαλύτερο ή ίσο του $((k+1)-2)2^{k+1} + 2$ .

Επίσης μπορώ να γράψω κάθε περιττό μεγαλύτερο ή ίσο του

$\displaystyle{ 2((k-2)2^k+2) + (2^{k+1}-1) = (k-1)2^{k+1}+3 = [(k+1)-2]2^{k+1} + 2.}$

Ο ισχυρισμός 1 αποδείχθηκε. Για να δείξω ότι δεν μπορώ να γράψω τον (n-2)2^n + 1

είναι πιο δύσκολο διότι δεν αποδεικνύεται επαγωγικά. Το κόλπο είναι να αποδείξω επαγωγικά κάτι αρκετά πιο ισχυρό. Δεν είναι εύκολο να βρεθεί ο ισχυρισμός αλλά βρήκα το πιο κάτω.

Ισχυρισμός 2: Αν $k,\ell$ φυσικοί με $\ell \geqslant 1$ και $k \geqslant 2\ell$ τότε δεν μπορώ να γράψω τον αριθμό $(n-k)2^n + \ell$ .

Με $k=2,\ell=1$ παίρνω ότι δεν μπορώ να γράψω τον (n-2)2^n+1

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

Απόδειξη ισχυρισμού: Με επαγωγή στο

. Για

ισχύει οπότε ας υποθέσω ότι ισχύει και για n=m

. Θέλω να δείξω ότι ισχύει για n=m+1

. Ας υποθέσω πως δεν ισχύει. Οπότε μπορώ να γράψω τον $(m+1-k)2^{m+1} + \ell$ για κάποια $k,\ell$ με $\ell \geqslant 1$ και $k \geqslant 2\ell$ . Αν πάρω

φορές τον $2^{m+1}-1$ σε αυτήν την γραφή τότε θα έχω

$\displaystyle{ r(2^{m+1}-1) + 2s =(m+1-k)2^{m+1} + \ell }$

όπου

είναι ένας αριθμός που μπορώ να γράψω με τα στοιχεία του A_m

. Είναι όμως

$\displaystyle{ s = (m+1-k-r)2^m + (\ell+r)/2 = (m - k')2^m + \ell'}$

όπου $\ell' = (\ell+r)/2$ και k' = k+r-1

.

Είναι $\ell' \geqslant \ell/2 \geqslant 1/2$ και επειδή

φυσικός τότε είναι και $\ell'$ φυσικός και άρα $\ell' \geqslant 1$ .

Επίσης έχω

$\displaystyle{ k' - 2\ell' = (k+r-1)- (\ell+r) = k-\ell-1 \geqslant \ell - 1 \geqslant 0 }$

Αυτό όμως είναι άτοπο από την επαγωγική υπόθεση.

#11

Βάζω άλλα τρία προβλήματα Συνδυαστικής.
Combinatorics 4
Υποθέτουμε ότι ένα πολύγωνο

με κορυφές σημεία του ακέραιου πλέγματος μπορεί να καλυφθεί με

τετρόμινο.
Να αποδειχθεί ότι αν καλύψουμε το

με

και

τετρόμινο, τότε πάντα χρησιμοποιούμε άρτιο πλήθος από

τετρόμινο.
Για το

και το

τετρόμινο δείτε εδώ http://en.wikipedia.org/wiki/Tetromino#cite_note-8

Το C5 (βελτιωμένο) μπήκε στο διαγωνισμό σαν πρόβλημα 6.

Combinatorics 6
Έχουμε μία άπειρη στήλη από κάρτες που καθεμιά έχει έναν πραγματικό αριθμό γραμμένο πάνω. Για κάθε πραγματικό αριθμό

υπάρχει ακριβώς μία κάρτα που έχει γραμμένο το

πάνω της. Δύο παίκτες παίρνουν δύο υποσύνολα ξένα υποσύνολα A,B

από 100 κάρτες ο καθένας. Θέλουμε να ορίσουμε έναν κανόνα που να αναδεικνύει έναν νικητή. Ο κανόνας αυτός πρέπει ικανοποιεί τις ακόλουθες συνθήκες:

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

β) Αν γράψουμε τα στοιχεία και των δύο συνόλων σε αύξουσα σειρά $A=\{a_1,...,a_{100}\}$ και $B=\{b_1,...,b_{100}\}$ και a_i>b_i

για κάθε

τότε ο

νικάει τον

γ) Αν τρεις παίκτες πάρουν υποσύνολα A,B,C

ώστε ο

νικά τον

και ο

τον

τότε ο

νικά τον

Πόσοι τρόποι υπάρχουν για να ορίσουμε έναν τέτοιο κανόνα; (Δύο ορισμοί θα είναι διαφορετικοί αν υπάρχουν δύο σύνολα A,B

ώστε με τον έναν κανόνα ο

να νικά τον

ενώ με τον άλλο κανόνα ο

να νικά τον

Combinatorics 7
Έστω

ένα σύνολο από $n\geq 4$ σημεία στο επίπεδο, ανά τρία μη συνευθειακά. Αρχικά τα σημεία συνδέονται με

τμήματα έτσι ώστε κάθε σημείο του

να είναι άκρο από ακριβώς δύο τμήματα. Ύστερα, σε κάθε βήμα, μπορούμε να διαλέξουμε δύο τμήματα AB,CD

που να έχουν κοινό εσωτερικό σημείο και να τα αντικαταστήσουμε με τα τμήματα AC,BD

αν κανένα από αυτά δεν υπάρχει ως τώρα. Να αποδειχθεί ότι δεν μπορούμε να κάνουμε n^3/4

ή περισσότερες τέτοιες κινήσεις.

#12

smar έγραψε:
Combinatorics 6
Έχουμε μία άπειρη στήλη από κάρτες που καθεμιά έχει έναν πραγματικό αριθμό γραμμένο πάνω. Για κάθε πραγματικό αριθμό υπάρχει ακριβώς μία κάρτα που έχει γραμμένο το πάνω της. Δύο παίκτες παίρνουν δύο υποσύνολα ξένα υποσύνολα από 100 κάρτες ο καθένας. Θέλουμε να ορίσουμε έναν κανόνα που να αναδεικνύει έναν νικητή. Ο κανόνας αυτός πρέπει ικανοποιεί τις ακόλουθες συνθήκες:

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

β) Αν γράψουμε τα στοιχεία και των δύο συνόλων σε αύξουσα σειρά $A=\{a_1,...,a_{100}\}$ και $B=\{b_1,...,b_{100}\}$ και για κάθε τότε ο νικάει τον

γ) Αν τρεις παίκτες πάρουν υποσύνολα ώστε ο νικά τον και ο τον τότε ο νικά τον

Πόσοι τρόποι υπάρχουν για να ορίσουμε έναν τέτοιο κανόνα; (Δύο ορισμοί θα είναι διαφορετικοί αν υπάρχουν δύο σύνολα ώστε με τον έναν κανόνα ο να νικά τον ενώ με τον άλλο κανόνα ο να νικά τον

Εκτός και αν κάτι χάνω είναι ουσιαστικά αρκετά γνωστό. Δείτε π.χ. εδώ: https://christofides.wordpress.com/2011 ... δικτατορία

Δεν μπαίνει σε link μάλλον λόγω των ελληνικών στην διεύθυνση.

gavrilos · #13

smar έγραψε:Number theory 2
Να προσδιορίσετε όλα τα ζεύγη θετικών ακεραίων που είναι τέτοια ώστε:
$\sqrt[3]{7x^2-13xy+7y^2}=|x-y|+1.$

Αν $\displaystyle{|x-y|\in \{0,1\}}$ παίρνουμε τη λύση $\displaystyle{(x,y)=(1,1)}$ .Έστω $\displaystyle{|x-y|\geq 2}$ .

Η σχέση γράφεται $\displaystyle{\sqrt[3]{7(x-y)^2+xy}=|x-y|+1\Leftrightarrow 7p^2+q=(p+1)^3}$ όπου $\displaystyle{p=|x-y|}$ και $\displaystyle{q=xy}$ .

Ισοδύναμα $\displaystyle{q=p^3-4p^2+3p+1}$ .Λόγω συμμετρίας υποθέτουμε ότι $\displaystyle{x\geq y}$ .

Τότε $\displaystyle{p=x-y}$ και τα $\displaystyle{x,-y}$ είναι ρίζες της εξίσωσης $\displaystyle{t^{2}-pt-q=0}$ .

Έχουμε $\displaystyle{\Delta =p^2+4(p^3-4p^2+3p+1)=4p^3-15p^2+12p+4=(p-2)^{2}(4p+1)}$ .

Επομένως $\displaystyle{x=\frac{p+(p-2)\sqrt{4p+1}}{2}}$ και $\displaystyle{-y=\frac{p-(p-2)\sqrt{4p+1}}{2}}$ .

Άρα αρκεί το $\displaystyle{4p+1}$ να είναι τέλειο τετράγωνο γιατί τότε οι παραπάνω παραστάσεις δίνουν ακέραιες ρίζες (με $\displaystyle{\mod 2}$ ).

Έστω $\displaystyle{4p+1=(2k+1)^2 \ , \ k\geq 1}$ .Τότε $\displaystyle{p=\frac{4k(k+1)}{4}=k(k+1)}$ .

Τότε $\displaystyle{x=\frac{k(k+1)+(k^2+k-2)(2k+1)}{2}=\frac{2k^3+4k^2-2k-2}{2}=k^3+2k^2-k-1}$ και

$\displaystyle{y=-\frac{k(k+1)-(k^2+k-2)(2k+1)}{2}=\frac{2k^3+2k^2-4k-2}{2}=k^3+k^2-2k-1}$ .

Αυτές οι λύσεις ικανοποιούν τις αρχικές υποθέσεις.Άρα $\displaystyle{(x,y)=(k^3+2k^2-k-1,k^3+k^2-2k-1),}$ και μεταθέσεις.

$\rule{430pt}{1pt}$

Αυτή η λύση είναι ιδέα που πήρα από μια λύση του Σιλουανού.

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

#14

gavrilos έγραψε: Αυτή η λύση είναι ιδέα που πήρα από μια λύση του Σιλουανού.

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

Ωραία Γιώργο!! Αυτή είναι η άσκηση http://artofproblemsolving.com/communit ... 93p4769940
Φαντάζομαι ότι απλά δεν ήθελαν να βάλουν το πρόβλημα όπως στην shortlist και το άλλαξαν.

#15

smar έγραψε:Βάζω άλλα τρία προβλήματα Συνδυαστικής.
Combinatorics 4
Υποθέτουμε ότι ένα πολύγωνο με κορυφές σημεία του ακέραιου πλέγματος μπορεί να καλυφθεί με τετρόμινο.
Να αποδειχθεί ότι αν καλύψουμε το με και ${\color{red} Z}$ τετρόμινο, τότε πάντα χρησιμοποιούμε άρτιο πλήθος από τετρόμινο.
Για το και το τετρόμινο δείτε εδώ http://en.wikipedia.org/wiki/Tetromino#cite_note-8

Χωρίς λόγια. (Προσθέστε τα.)

gavrilos · #16

smar έγραψε:Number theory 1
Έστω $n\geq 2$ ένας ακέραιος και $A_n=\{2^n-2^k\ |k\in\mathbb{Z},\ 0\leq k<n\}.$

Να προσδιοριστεί ο μεγαλύτερος θετικός ακέραιος που δεν μπορεί να γραφεί σαν άθροισμα ενός ή περισσότερων (όχι αναγκαστικά διαφορετικών) στοιχείων του

Έχω την ίδια λύση με τον κύριο Δημήτρη με μια διαφορά στο τελείωμα.Τη βάζω αλλά με επιφύλαξη.

$\displaystyle{n}$ -καλός είναι ο αριθμός που γράφεται ως άθροισμα στοιχείων του $\displaystyle{A_{n}}$ .

Έστω $\displaystyle{f(n)}$ ο μέγιστος $\displaystyle{n}$ -μη καλός.Οι μικρές περιπτώσεις επαληθεύουν τον τύπο $\displaystyle{f(n)=(n-2)2^{n}+1}$ .

Άρα μπορούμε να υποθέσουμε ότι $\displaystyle{f(k)=(k-2)2^{k}+1}$ για κάποιο $\displaystyle{k}$ .

Όπως και ο κύριος Δημήτρης αποδεικνύω με επαγωγή ότι κάθε αριθμός μεγαλύτερος ή ίσος του $\displaystyle{(k-1)2^{k+1}+2}$ είναι $\displaystyle{(k+1)}$ -καλός.

Έστω τώρα πως ο $\displaystyle{M=(k-1)2^{k+1}+1}$ είναι $\displaystyle{(k+1)}$ -καλός.

Επειδή είναι περιττός,το άθροισμα θα περιέχει περιττό πλήθος όρων ίσων με $\displaystyle{2^{k+1}-1}$ .Άρα ο $\displaystyle{M'=M-2^{k+1}+1=(k-2)2^{k+1}+2}$ είναι $\displaystyle{(k+1)}$ -καλός.

Έστω $\displaystyle{M'=S+2m(2^{k+1}-1)}$ όπου $\displaystyle{S}$ άθροισμα όρων του $\displaystyle{A_{k+1}}$ διαφορετικών του $\displaystyle{2^{k+1}-1}$ .

Τότε με την παρατήρηση ότι για κάθε στοιχείο $\displaystyle{a_{i}\in A_{k+1}}$ εκτός του $\displaystyle{2^{k+1}-1}$ υπάρχει στοιχείο του $\displaystyle{b_{j}\in A_{k}}$ με $\displaystyle{a_{i}=2b_{j}}$ και αντίστροφα,

έχουμε πως ο αριθμός $\displaystyle{S'=\frac{S}{2}}$ είναι άθροισμα στοιχείων του $\displaystyle{A_{k}}$ .

Επίσης $\displaystyle{2^{k+1}-1=2^{k-1}+2^{k-1}+(2^{k}-1)}$ και $\displaystyle{2^{k-1},2^{k}-1\in A_{k}}$ .

Επομένως ο $\displaystyle{\frac{M'}{2}=S'+m(2^{k-1}+2^{k-1}+2^{k}-1)}$ είναι $\displaystyle{k}$ -καλός,που είναι άτοπο από την επαγωγική υπόθεση,και το ζητούμενο αποδείχθηκε.

Edit:Τυπογραφικό.

#17

gavrilos έγραψε:
smar έγραψε:Number theory 1
Έστω $n\geq 2$ ένας ακέραιος και $A_n=\{2^n-2^k\ |k\in\mathbb{Z},\ 0\leq k<n\}.$

Να προσδιοριστεί ο μεγαλύτερος θετικός ακέραιος που δεν μπορεί να γραφεί σαν άθροισμα ενός ή περισσότερων (όχι αναγκαστικά διαφορετικών) στοιχείων του
Έχω την ίδια λύση με τον κύριο Δημήτρη με μια διαφορά στο τελείωμα.

Η διαφορά είναι ότι το τελείωμα είναι πιο απλό από το δικό μου.

GVlachos · #18

smar έγραψε:

Combinatorics 7
Έστω ένα σύνολο από $n\geq 4$ σημεία στο επίπεδο, ανά τρία μη συνευθειακά. Αρχικά τα σημεία συνδέονται με τμήματα έτσι ώστε κάθε σημείο του να είναι άκρο από ακριβώς δύο τμήματα. Ύστερα, σε κάθε βήμα, μπορούμε να διαλέξουμε δύο τμήματα που να έχουν κοινό εσωτερικό σημείο και να τα αντικαταστήσουμε με τα τμήματα αν κανένα από αυτά δεν υπάρχει ως τώρα. Να αποδειχθεί ότι δεν μπορούμε να κάνουμε ή περισσότερες τέτοιες κινήσεις.

Λήμμα 1: Έστω Σ το σύνολο των

τμημάτων. Θεωρούμε μια ευθεία στο επίπεδο, που δεν τέμνει το σύνολο Μ, και έστω ότι τέμνει κ το πλήθος τμήματα του Σ. Τότε αν η ευθεία αφήνει τα Α,Γ σε διαφορετικό ημιεπίπεδο από τα Β,Δ, τότε μια εφαρμογή της κίνησης στα ΑΒ,ΓΔ μειώνει το πλήθος των τμημάτων που τέμνουν την ευθεία σε κ-2.
Επίσης οποιαδήποτε κίνηση δεν μπορεί να αυξήσει το πλήθος των τμημάτων που τέμνουν την ευθεία. Με άλλα λόγια το πλήθος των τμημάτων που τέμνει την ευθεία φθίνει κατά την εφαρμογή των κινήσεων

Θα ορίσουμε τώρα ένα σύνολο ευθειών Τ, έτσι ώστε για κάθε τετράδα σημείων Α,Β,Γ,Δ (με ΑΒ να τέμνει το ΓΔ) του Μ, να υπάρχει ευθεία του Τ που να αφήνει τα Α,Γ σε διαφορετικό ημιεπίπεδο από τα Β,Δ. Σε αυτή την περίπτωση θα λέμε πως η ευθεία διαχωρίζει τα Α,Β,Γ,Δ.
Τότε από το Λήμμα 1, κάθε κίνηση θα μειώνει το πλήθος των σημείων της τομής του Σ με το Τ κατά τουλάχιστον 2. Άρα, μπορούμε να κάνουμε το πολύ |Σ $\cap$ T|/2 κινήσεις.

Λήμμα 2: Για κάθε σημείο Α του Μ που βρίςκεται στο boundary του convex hull, υπάρχουν ευθείες που διαχωρίζουν όλες τις τετράδες που περιέχουν το Α και τέμνουν το Σ σε n^2 το πολύ σημεία.
Απόδειξη: Με κέντρο το Α, ονομάζουμε τα υπόλοιπα σημεία $u_1,..,u_{n-1}$ σε clockwise order. Οπότε υπάρχει ευθεία που αφήνει τα Α, $u_1,u_2,..,u_{i-1},u_i$ σε διαφορετικό ημιεπίπεδο από τα υπόλοιπα σημεία. Έστω L_i

αυτή η ευθεία. Τότε η L_i

τέμνει το Σ σε 2i το πολύ σημεία για $i \leq (n-1)/2$ , αλλιώς σε (n-i)/2 το πολύ σημεία. Έτσι έχουμε λιγότερες από n^2/2 τομές. Ορίζοντας αντίστοιχα και τις ευθείες που αφήνουν τα $u_1,u_2,..,u_{i-1},u_i$ σε διαφορετικό ημιεπίπεδο από τα υπόλοιπα σημεία, παίρνουμε άλλες n^2/2 τομές. Εύκολα βλέπουμε ότι αυτές οι ευθείες διαχωρίζουν κάθε τετράδα που περιέχει το Α.

Οπότε από το Λήμμα 2, με επαγωγή παίρνουμε ένα σύνολο ευθειών Τ που διαχωρίζει όλες τις τετράδες και τέμνει το Σ σε λιγότερα από 1^2+2^2+3^2+..+n^2<(n+1)^3/3

σημεία. Οπότε μπορούμε να κάνουμε το πολύ (n+1)^3/6

κινήσεις.

#19

Γιώργο, ευχαριστούμε για την λύση του C7!

Να προσθέσω ότι χθες βράδυ ο Γιώργος μου είπε και την σωστή λύση του C2. (Η έμφαση δική μου.)

Θεωρούμε το γινόμενο

των αριθμών. Σε κάθε βήμα το

πολλαπλασιάζεται με $\displaystyle{ \frac{(a+b)2}{ab} \geqslant 4.}$ Αρχικά το γινόμενο είναι

οπότε στο τέλος θα έχουμε $P_{final} \geqslant 4^{m2^{m-1}}$ και άρα από την ανισότητα ΑΜ-ΓΜ θα έχουμε και

$\displaystyle{ S_{final} \geqslant 2^m P_{final}^{2^{-m}} = 2^m 4^{m/2} = 4^m.}$

#20

smar έγραψε: Algebra 4
Να προσδιορίσετε όλες τις συναρτήσεις $f:\mathbb{Z}\rightarrow\mathbb{Z}$ που ικανοποιούν την εξίσωση:

Έστω ότι

.

Για

παίρνω $k \neq 0$ .

Για m=0

παίρνω

για κάθε $n \in \mathbb{Z}$ .

Επαγωγικά από το προηγούμενο βγάζω

$f(n+rk) = f(n) + 2014r \quad (\ast)$

για κάθε $n,r \in \mathbb{Z}$ . (Ουσιαστικά είναι δύο επαγωγές. Μια για θετικά

και μια για αρνητικά.)

Ειδικά για n=0

είναι

$f(rk) = k + 2014r \quad (\ast \ast)$

Για m=k^2

στην αρχική και χρησιμοποιώντας την $(\ast \ast)$ έχουμε

$\displaystyle{ f(n+2015k) = f(n) + (2k+1) \cdot 2014.}$

Όμως από την $(\ast)$ είναι και

$\displaystyle{ f(n+2015k) = f(n) + 2015 \cdot 2014}$

οπότε από τις τελευταίες δύο ισότητες καταλήγω στο k=1007

.

Έστω τώρα $m \in \mathbb{Z}$ και έστω ότι f(m) = a

και

. Η αρχική ισότητα δίνει

$\displaystyle{ f(n+a) = f(n) + (2014+b-a)}$

για κάθε $n \in \mathbb{Z}$ το οποίο επαγωγικά δίνει

$\displaystyle{ f(n+1007a) = f(n) + 1007(2014+b-a)}$

Όμως από την $(\ast)$ , αφού k=1007

παίρνω

$\displaystyle{ f(n+1007a) = f(n) + 2014a}$

και οι τελευταίες δύο δίνουν 3a = 2014+b

, δηλαδή

.

Επαγωγικά παίρνω

$\displaystyle{ f(3^r m) = 3^r f(m) - (3^r-1)1007 \quad (\dagger) }$

για κάθε φυσικό

.

Έχω $1007 = 19 \cdot 53$ οπότε $\varphi(1007) = 18 \cdot 52 = 936$ και άρα $3^{936} \equiv 1 \bmod 1007$ αφού (3,1007) = 1

.

H $(\dagger)$ για r = 936

δίνει

$\displaystyle{ f(3^{936}m) = 3^{936}f(m) - (3^{936}-1)1007}$

H $(\ast \ast)$ όμως, αφού k= 1007

, για $n=m,r = (3^{936}-1)m/1007$ δίνει

$\displaystyle{ f(3^{936}m) = f(m) +2014r = f(m) + 2m(3^{936}-1).}$

Τώρα μπορούμε να λύσουμε τις τελευταίες δύο ως προς f(m)

και θα πάρουμε

f(m) = 1007+2m

.

Εύκολα ελέγχεται ότι ικανοποιεί την συναρτησιακή εξίσωση οπότε είναι και μοναδική λύση.

IMO 2014 (Shortlisted Problems)

IMO 2014 (Shortlisted Problems)

Re: IMO 2014 (Shortlisted Problems)

Re: IMO 2014 (Shortlisted Problems)

Re: IMO 2014 (Shortlisted Problems)

Re: IMO 2014 (Shortlisted Problems)

Re: IMO 2014 (Shortlisted Problems)

Re: IMO 2014 (Shortlisted Problems)

Re: IMO 2014 (Shortlisted Problems)

Re: IMO 2014 (Shortlisted Problems)

Re: IMO 2014 (Shortlisted Problems)

Re: IMO 2014 (Shortlisted Problems)

Re: IMO 2014 (Shortlisted Problems)

Re: IMO 2014 (Shortlisted Problems)

Re: IMO 2014 (Shortlisted Problems)

Re: IMO 2014 (Shortlisted Problems)

Re: IMO 2014 (Shortlisted Problems)

Re: IMO 2014 (Shortlisted Problems)

Re: IMO 2014 (Shortlisted Problems)

Re: IMO 2014 (Shortlisted Problems)

Re: IMO 2014 (Shortlisted Problems)

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