ΙΜΟ Μικρή Λίστα 2015

GVlachos · #21

silouan έγραψε: Βάζω ένα διαφορετικό τελείωμα από εδώ και πέρα: (Μπορεί να το ελέγξει κάποιος; )
Είναι άμεσο ότι αν $s,t\in S$ με τότε η άρτια αναπαράσταση του περιέχει το .
Οπότε για κάθε θα έχουμε ότι γράφεται στη μορφή $s_j=s_{j-1}+\ldots+s_z+Y_j$ όπου το είναι το υπόλοιπο, δηλαδή άθροισμα στοιχείων $s_1,\ldots, s_{z-1}$
Παίρνω το δείκτη με το μικρότερο υπόλοιπο. Τότε από την επιλογή του
$\displaystyle s_{j_0+1}=s_z+s_{z+1}+\ldots+s_{j_0}+Y_{j_0+1}=(s_{j_0}-Y_{j_0})+s_{j_0}+Y_{j_0+1}\geqslant 2s_{j_0}$ επομένως η άρτια αναπαράσταση του $2s_{j_0}$ πρέπει να περιέχει το $s_{j_0}$ οπότε αφαιρώντας το παίρνουμε ότι $s_{j_0}$ έχει περιττή αναπαράσταση διαφορετική από τον εαυτό του, άτοπο.

Πολύ ωραία λύση Σιλουανέ!

GVlachos · #22

Ας δούμε κι αυτό.
Όμορφο θέμα, αλλά πολύ εύκολο για

.

silouan έγραψε: Ν6. Έστω μία συνάρτηση $f:\mathbb{Z}_{>0}\rightarrow\mathbb{Z}_{>0}$ για την οποία ισχύουν τα ακόλουθα:

α) Αν $m,n\in\mathbb{Z}_{>0}$ τότε o $\displaystyle\frac{f^{n}(m)-m}{n}$ είναι θετικός ακέραιος.

β) το σύνολο $\mathbb{Z}_{>0}\setminus\{ f(n)|n\in\mathbb{Z}_{>0}\}$ είναι πεπερασμένο.

Δείξτε ότι η ακολουθία είναι περιοδική.

Σημείωση: Με $f^{n}(m)$ συμβολίζουμε τη σύνθεση της φορές με τον εαυτό της.

Η

είναι

, γιατί αν f(a)=f(b)

, τότε

$\forall n$ . Επίσης από τη συνθήκη (α) παίρνουμε f(m)>m

$\forall m$ .
Έστω $S=\{s_1,..,s_z\}\subset Z_{>0}$ το σύνολο των θετικών ακεραίων που δεν ανήκουν στην εικόνα της

. Θέτουμε $A_i=\{f^n(i)|n \in Z_{\geq0}}\}$ , όπου f^0(i)=i

.
Είναι άμεσο ότι κάθε θετικός ακέραιος περιέχεται σε ακριβώς ένα A_i

.

Λήμμα 1: Για κάθε A_i

η ακολουθία $f^{n+1}(i)-f^n(i)$ είτε είναι σταθερή, είτε $\frac{|\{k|f^k(i)<n\}|}{n}\to 0$ .
Απόδειξη:
Έστω $c=f^{n+1}(i)-f^n(i) < f^{k+1}(i)-f^k(i)=d$ . Τότε για κάθε p>10max(d,k,n)

, έχουμε $(p-n)|((f^{p+1}(i)-f^p(i))-c)$ και $(p-k)|((f^{p+1}(i)-f^p(i))-d)$ . Οι 2 αυτές σχέσεις άμεσα δίνουν $f^{p+1}(i)-f^p(i)\geq min(p-n-c, p-k-d)>\frac{p}{2}$ για κάθε

αρκετά μεγάλο και το ζητούμενο έπεται εύκολα.

Αν τα A_i

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

το lcm των περιόδων τους και

ένας ακέραιος που δεν περιέχεται στις προόδους. Τότε η ακολουθία N+kL

δεν τέμνει τις προόδους, άρα θα πρέπει να καλύπτεται από τα A_i

που δεν είναι αριθητικές πρόοδοι. Αυτό όμως δε μπορεί να συμβαίνει, αφού $\frac{|\{k|N+kL<n\}|}{n}\to \frac{1}{L}>0$

GVlachos · #23

Το πιο ωραίο για μένα πρόβλημα της λίστας.

silouan έγραψε:
Ν8. Για κάθε θετικό ακέραιο $n=\prod_{i=1}^k p_i^{a_i}$ ορίζουμε
$\displaystyle\mho(n)=\sum_{i: p_i>10^{100}}a_i$ .

Να βρεθούν όλες οι γνησίως αύξουσες συναρτήσεις $f:\mathbb{Z}\rightarrow\mathbb{Z}$ ώστε
$\displaystyle\mho (f(a)-f(b))\leqslant\mho (a-b)$

Για $n=\prod_{i=1}^k p_i^{a_i}$ θέτουμε $Q(n)=\prod_{i: p_i>10^{100}} p_i^{a_i}$ .

Λήμμα 1:
Q(a-b)=Q(f(a)-f(b))

Απόδειξη:
Έστω $1<d_1<d_2<\cdots$ η ακολουθία όλων των θετικών ακεραίων που δεν έχουν πρώτο διαιρέτη μικρότερο του $10^{100}$ .
Θα αποδείξουμε με επαγωγή πάνω στα d_i

ότι $Q(a-b)=d_i \Leftrightarrow Q(f(a)-f(b))=d_i$ .
Βασικό βήμα:
Έστω a-b=d_1

. Ο

είναι πρώτος και οι $f(a),f(a+1),\ldots, f(b)$ δίνουν τουλάχιστον d_1+1

υπόλοιπα modulo d_1

, άρα έχουμε $a\leq x \leq y \leq b$ με d_1|(f(x)-f(y))

, οπότε

και

. Οπότε $Q(a-b)=d_1 \Rightarrow d_1|(f(a)-f(b))$ και άρα από τη συνθήκη $\displaystyle\mho (f(a)-f(b))\leqslant\mho (a-b)$ , παίρνουμε $Q(a-b)=d_1 \Leftrightarrow Q(f(a)-f(b))=d_1$
Επαγωγική υπόθεση:
Για $i\leq n$ ισχύει $Q(a-b)=d_i \Leftrightarrow Q(f(a)-f(b))=d_i$ .
Επαγωγικό βήμα:
Έστω $a-b=d_{n+1}$ , τότε οι $f(a),f(a+1),\ldots, f(b)$ δίνουν τουλάχιστον $d_{n+1}+1$ υπόλοιπα modulo $d_{n+1}$ , άρα έχουμε $a\leq x \leq y \leq b$ με $d_{n+1}|(f(x)-f(y))$ .
Αν x-y < a-b

, τότε

με

, οπότε από την επαγωγική υπόθεση $Q(f(y)-f(x))=Q(y-x)=d_i<d_{n+1}$ . Άτοπο, αφού είναι αδύνατον να έχουμε ταυτόχρονα $Q(x-y)<d_{n+1}$ και $d_{n+1}|Q(x-y)$ . Οπότε x=a,y=b

και $Q(f(a)-f(b))=d_{n+1}$ για $a-b=d_{n+1}$ .
Είναι άμεσο ότι $Q(a-b)=d_{n+1} \Rightarrow d_{n+1}|Q(f(a)-f(b))$ και άρα από τη συνθήκη $\displaystyle\mho (f(a)-f(b))\leqslant\mho (a-b)$ παίρνουμε $Q(a-b)=d_{n+1} \Leftrightarrow Q(f(a)-f(b))=d_{n+1}$ .

Λήμμα 2:
Υπάρχει K>0

τέτοιο ώστε f(x) <Kx

για

.
Απόδειξη:
Θέτουμε $S=\{n|n\in Z \cap [0,10^{100}]\}$ και $R = \prod_{ n,m \in S, n<m} (f(m)-f(n))$ , $T= \prod_{ n \in S} n^R$ . Εύκολα προκύπτει ότι για x>2T

και για κάθε πρώτο $p \in S$ , το $p^{R+1}$ διαιρεί το πολύ έναν εκ των $f(x),f(x-1),\ldots, f(x-10^{100})$ . Άρα για κάποιο $i \in S$ , $f(x-i) \leq TQ(x-i) \leq T(x-i) \Rightarrow f(x-10^{100}) <2T(x-10^{100}) \Rightarrow f(y) <2Ty$ για y>2T

.

Λήμμα 3:
Για κάθε $\epsilon>0$ υπάρχει $N_{\epsilon}>0$ ώστε $\frac{x!}{Q(x!)}<x!^{\epsilon}, \forall x>N_{\epsilon}$ .
Απόδειξη:
Για κάθε πρώτο

, εύκολα δείχνουμε ότι $p^{x}\nmid x!$ . Άρα $\frac{x!}{Q(x)}<T^x$ και το ζητούμενο έπεται.

Λήμμα 4:
Για κάθε $M, \epsilon>0$ υπάρχει x>M

με $\frac{x}{Q(x)}<x^{\epsilon},\frac{x+1}{Q(x+1)}<x^{\epsilon},\frac{x+2}{Q(x+2)}<x^{\epsilon}$ .
Απόδειξη:
Έστω ότι δεν υπάρχει τέτοιο

μεγαλύτερο από κάποιο

. Τότε για κάθε 3 διαδοχικούς ακέραιους μεγαλύτερους του

, για κάποιον

από αυτούς θα ισχύει $\frac{y}{Q(y)}\geq y^{\epsilon}$ , που δίνει $\frac{x!}{Q(x!)}> \frac{1}{2}(x!^{\frac{\epsilon}{3}})$ για

μεγάλο (λόγω της πολλαπλασιατικότητας της συνάρτησης

). Άτοπο από το Λήμμα 3.

Λήμμα 5:
Για κάθε

έχουμε

.
Απόδειξη:
Έστω ότι υπάρχει

με $f(a+1)-f(a)=k \neq l=f(a+2)-f(a+1)$ . Χωρίς βλάβη της γενικότητας μπορούμε να υποθέσουμε a=1

και

, που δίνει f(0)=0,f(1)=c,f(2)=k, f(3)=l

. Επιλέγουμε ένα

όπως στο Λήμμα 4 και έχουμε $Q(x), Q(x+1), Q(x+2) \geq x^{\epsilon}$ και τις 3 σχέσεις διαιρετότητας:
Q(x+2)|f(x+2)

Από την 1η σχέση f(x+2)=rQ(x+2)

. Ξέρουμε επίσης ότι $Q(x+2) \frac{x+2}{Q(x+2)} \equiv 1 (mod Q(x+1)$ . Με τη 2η σχέση παίρνουμε:
$rQ(x+2) \equiv k \equiv k Q(x+2)\frac{x+2}{Q(x+2)} (mod Q(x+1)) \Rightarrow$
$\Rightarrow r\equiv k \frac{x+2}{Q(x+2)} (mod Q(x+1))$
Υποθέτουμε

μεγάλο, οπότε τα Λήμματα 2,4 δίνουν r<Q(x+1)

και άρα $r = k \frac{x+2}{Q(x+2)} < Q(x+1)$ .
Τέλος, $Q(x)|f(x+2)-k-l = k(x+2)-k-l = kx+ (k-l)\Rightarrow Q(x)|k-l$ . Άτόπο, αφού $k\neq l$ και |k-l|<x

.

Από το Λήμμα 5 προκύπτει άμεσα ότι οι συναρτήσεις που ικανοποιούν τις συνθήκες είναι ακριβώς οι αριθμητικές πρόοδοι με διαφορά d>0

και $p|d \Rightarrow p < 10^{100}$ για κάθε πρώτο

.

*Μπορούμε να παραλείψουμε τα βήματα 3,4 με χρήση του θεωρήματος του Dirichlet για τις αριθμητικές προόδους.

#24

silouan έγραψε: C7. Σε μία εταιρία υπάρχουν κάποια ζεύγη ανθρώπων που είναι εχθροί. Ένα γκρουπ ανθρώπων θα ονομάζεται ακοινώνητο, αν το πλήθος των μελών του είναι περιττός αριθμός, τουλάχιστον 3, και είναι δυνατόν να τοποθετήσουμε όλα τα μέλη του σε ένα κυκλικό τραπέζι, ώστε κάθε δύο γειτονικά άτομα να είναι εχθροί.
Αν δίνεται ότι υπάρχουν το πολύ ακοινώνητα γκρουπ, να αποδείξετε ότι είναι δυνατόν να διαμερίσουμε την εταιρία σε 11 μέρη, έτσι ώστε να μην υπάρχουν εχθροί στο ίδιο μέρος.

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

Αρκεί να δείξω ότι κάθε γράφημα

με χρωματικό αριθμό $\chi(G) = n$ έχει τουλάχιστον $2^{n-1} - n$ κυκλικά υποσύνολα. [Πράγματι κατασκευάζω το γράφημα

με κορυφές τα μέλη της εταιρίας και ακμές μεταξύ δύο μελών αν και μόνο αν είναι εχθροί. Αν δεν μπορούμε να διαμερίσουμε την εταιρία όπως ζητείται τότε είναι $\chi(G) \geqslant 12$ και άρα υπάρχουν τουλάχιστον $2^{11} - 12 > 2015$ κυκλικά υποσύνολα. Κάθε όμως κυκλικό υποσύνολο είναι ένα ακοινώνητο γκρουπ ανθρώπων, άτοπο.]

Θα προχωρήσω με επαγωγή στο

. Οι περιπτώσεις n=1,2

είναι άμεσες ενώ η περίπτωση n=3

είναι το γνωστό αποτέλεσμα ότι $\chi(G) \geqslant 3$ αν και μόνο αν το

περιέχει έναν περιττό κύκλο.

Ας υποθέσουμε λοιπόν ότι το αποτέλεσμα ισχύει για n=k

και έστω γράφημα

με $\chi(G) = k+1$ . Αν μπορώ να αφαιρέσω κορυφή από το

ώστε το γράφημα που παραμένει να εξακολουθεί να έχει χρωματικό αριθμό k+1

τότε το κάνω. Ασφαλώς τα κυκλικά υποσύνολα δεν αυξάνονται. Μπορώ να υποθέσω λοιπόν πως οποιαδήποτε κορυφή

του

και να αφαιρέσω θα έχω $\chi(G - v) = k$ .

Παίρνω λοιπόν μια κορυφή

. Έχουμε $\chi(G-v) = k$ άρα από την επαγωγική υπόθεση το G-v

έχει τουλάχιστον $2^{k-1} - k$ περιττά υποσύνολα. Αρκεί λοιπόν να δείξω πως το

έχει τουλάχιστον
$\displaystyle{ (2^k - (k+1)) - (2^{k-1} - k) = 2^{k-1} - 1}$
περιττά υποσύνολα τα οποία περιέχουν την κορυφή

.

Έστω $V_1,\ldots,V_k$ μια διαμέριση του G-v

σε ανεξάρτητα σύνολα. Το σύνολο $\{1,2,\ldots,k\}$ έχει $2^{k-1}-1$ άρτια και μη κενά υποσύνολα. Αρκεί για κάθε τέτοιο υποσύνολο

να δείξω ότι το

έχει ένα κυκλικό υποσύνολο το οποίο περιέχει την κορυφή

, τουλάχιστον μία κορυφή από κάθε V_i

με $i \in I$ και καμία κορυφή από κάποιο V_j

με $j \notin I$ .

Χωρίς βλάβη της γενικότητας έστω $I = \{1,2,\ldots,2r\}$ .

Για $1 \leqslant i \leqslant 2r$ έστω A_i

οι γειτονικές κορυφές του

στο

. Έστω επίσης B_i

το σύνολο όλων των κορυφών του V_i

για τις οποίες υπάρχει μονοπάτι $v_1v_2 \cdots v_t$ όπου $v_1 \in A_1$ και όπου $v_i \in V_{j(i)}$ όπου j(i)

το μοναδικό στοιχείο του

με $j(i) \equiv i \bmod 2r$ .

Θα δείξω ότι $A_{2r} \cap B_{2r} \neq \emptyset$ . Τότε θα έχω τελειώσει. Πράγματι τότε παίρνω ένα μονοπάτι $v_1 \cdots v_t$ με $v_1 \in A_1$ και $v_t \in A_{2r} \cap B_{2r}$ . Το μήκος του μονοπατιού είναι περιττό (αφού $t \equiv 2r \bmod 2r$ ) και έχει τουλάχιστον μία κορυφή από κάθε ένα από τα $V_1,\ldots,V_{2r}$ . Επίσης δεν έχει κορυφή από άλλο V_j

. Οπότε ο $vv_1\cdots v_tv$ είναι το κυκλικό υποσύνολο που θέλω με την ζητούμενη ιδιότητα.

Μένει λοιπόν να δείξω ότι $A_{2r} \cap B_{2r} \neq \emptyset$ . Ας υποθέσω ότι συμβαίνει το αντίθετο. Ορίζω $V_i' = (V_i \setminus B_i) \cup B_{i-1}$ όπου $B_0 = B_{2r}$ . Τα σύνολα V_i'

είναι ανεξάρτητα. Πράγματι αν υπήρχε ακμή

με $u \in B_{i-1}$ και $w \in V_i$ τότε εξ ορισμού θα είχαμε $w \in B_i$ και άρα $w \notin V_i'$ . Επιπλέον επειδή $A_1 \subseteq B_1$ και επειδή $A_{2r} \cap B_{2r} = \emptyset$ , το

δεν έχει γειτονικές κορυφές στο $V_1' = (V_1 \setminus B_1) \cup B_{2r}$ . Τότε όμως βάζοντας την

στο

παίρνω ότι το

έχει χρωματικό αριθμό

. Αυτό είναι άτοπο οπότε η απόδειξη ολοκληρώθηκε.

simantiris j. · #25

silouan έγραψε:Να συνεχίσουμε με τη συνδυαστική:

C1. Σε μία ευθεία υπάρχουν $n\geq 1$ πόλεις. Κάθε πόλη έχει μία αριστερή μπουλντόζα (στα αριστερά της πόλης και στραμμένη στα αριστερά) και μία δεξιά μπουλντόζα (στα δεξιά της πόλης και στραμμένη στα δεξιά). Όλες οι μπουλντόζες έχουν διαφορετικά μεγέθη. Οι μπουλντόζες ξεκινάνε να κινούνται προς την κατεύθυνσή της η καθεμιά και όταν μία δεξιά μπουλντόζα συναντήσει μία αριστερή, τότε η μεγαλύτερη βγάζει τη μικρότερη εκτός δρόμου (όπου και παραμένει αυτή εκεί). Επιπλέον αν κάποια στιγμή μία μπουλντόζα είναι πίσω από μία άλλη (έχουν δηλαδή την ίδια διεύθυνση), τότε η πίσω βγάζει την μπροστινή εκτός δρόμου, ανεξαρτήτως μεγεθών.
Έστω τώρα δύο πόλεις και με την να είναι δεξιά της . Θα λέμε ότι η πόλη εξοβελίζει την πόλη αν η δεξιά μπουλντόζα της μπορεί να φτάσει στην πόλη βγάζοντας από το δρόμο όλες τις μπουλντόζες που συναντά. Όμοια, θα λέμε ότι η πόλη εξοβελίζει την πόλη αν αριστερή μπουλντόζα της μπορεί να φτάσει στην πόλη βγάζοντας από το δρόμο όλες τις μπουλντόζες που συναντά.
Να αποδείξετε ότι υπάρχει ακριβώς μία πόλη που δεν μπορεί να εξοβελιστεί από καμιά άλλη.

Καλημέρα!Συγγνώμη που επαναφέρω το θέμα αλλά ήθελα να ρωτήσω αν είναι σωστή η λύση μου.
Θα προχωρήσουμε με ισχυρή επαγωγή στο

.Για

το ζητούμενο είναι προφανές.Έστω ότι ισχύει για 1,...,n-1

.Θα αποδείξουμε το ζητούμενο και για

πόλεις.
Βάζουμε τους αριθμούς 1,2,..,n

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

.
$\cdot$ Αν k=n

τότε η μπουλντόζα της πόλης αυτής νικάει όλες τις υπόλοιπες μπουλντόζες άρα δε μπορεί να εξοβελιστεί από καμιά άλλη πόλη και έχουμε το ζητούμενο.
$\cdot$ Αν $1<k\leq n-1$ τότε ανάμεσα στις τελευταίες n-k+1

πόλεις από επαγωγική υπόθεση υπάρχει μια που δεν μπορεί να εξοβελιστεί από καμιά από τις υπόλοιπες n-k

.Επίσης η αριστερή μπουλντόζα της πόλης

βγάζει εκτός δρόμου όλες τις μπουλντόζες των πολέων 1,..,k-1

άρα και καμιά από αυτές τις πόλεις δε μπορεί να εξοβελίσει την πόλη που είπαμε ότι υπάρχει από επαγωγική υπόθεση.Άρα αυτή η πόλη δε μπορεί να εξοβελιστεί από καμιά άλλη πόλη,ολοκληρώνοντας την επαγωγή.
Αποδείξαμε ότι υπάρχει μια πόλη που δεν εξοβελίζεται από τις υπόλοιπες.Για το ακριβώς μια μπορούμε να χρησιμοποιήσουμε τον Ισχυρισμό 2 στη λύση του κ.Δημήτρη τελείωνοντας το πρόβλημα.
Ένα πιθανό κενό υπάρχει για k=1

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

ΙΜΟ Μικρή Λίστα 2015

Re: ΙΜΟ Μικρή Λίστα 2015

Re: ΙΜΟ Μικρή Λίστα 2015

Re: ΙΜΟ Μικρή Λίστα 2015

Re: ΙΜΟ Μικρή Λίστα 2015

Re: ΙΜΟ Μικρή Λίστα 2015

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