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

#1

Ξεκινάω να βάζω και τα θέματα της περσινής λίστας από την ΙΜΟ.

Α1. Για την ακολουθία των θετικών πραγματικών $a_1, a_2,\ldots$ ισχύει ότι: $\displaystyle a_{k+1}\geq\frac{ka_k}{a_k^2+k-1}$ για κάθε θετικό ακέραιο

.
Να αποδείξετε ότι $a_1+a_2+\ldots+a_n\geq n$ για κάθε $n\geq 2$ .

A2. Να βρεθούν όλες οι συναρτήσεις $f:\mathbb{Z}\rightarrow\mathbb{Z}$ που ικανοποιούν την

f(x-f(y))=f(f(x))-f(y)-1

για κάθε $x,y\in\mathbb{Z}$ .

A3. Σταθεροποιούμε έναν θετικό ακέραιο

. Να βρεθεί η μέγιστη τιμή του

$\displaystyle\sum_{1\leq r<s\leq 2n} (s-r-n)x_rx_s$ ,

όπου $-1\leq x_i\leq 1$ για κάθε $i=1,2,\ldots, 2n$ .

A4. Να βρεθούν όλες οι συναρτήσεις $f:\mathbb R\to\mathbb R$ που ικανοποιούν την
$\displaystyle f(x+f(x+y))+f(xy)=x+f(x+y)+yf(x)$ για όλους τους πραγματικούς

και

.

Α5. Με $2\mathbb{Z}+1$ συμβολίζουμε το σύνολο των περιττών ακεραίων. Να βρεθούν όλες οι συναρτήσεις $f:\mathbb{Z}\rightarrow 2\mathbb{Z}+1$
που είναι τέτοιες ώστε
$\displaystyle f(x+f(x)+y)+f(x-f(x)+y)=f(x+y)+f(x-y)$ για κάθε $x,y\in\mathbb{Z}$ .

A6. Σταθεροποιούμε έναν ακέραιο $n\geq 2$ . Θα λέμε ότι δύο πολυώνυμα

και

με πραγματικούς συντελεστές είναι όμοια αν για κάθε $i=1,2,\ldots, n$ οι ακολουθίες $P(2015i), P(2015i-1),\ldots, P(2015i-2014)$ και $Q(2015i), Q(2015i-1),\ldots, Q(2015i-2014)$ είναι μετάθεση η μία της άλλης.

α) Να αποδείξετε ότι υπάρχουν δύο διαφορετικά πολυώνυμα βαθμού n+1

που είναι όμοια.
β) Να αποδείξετε ότι δεν υπάρχουν δύο διαφορετικά πολυώνυμα βαθμού

που είναι όμοια.

Σχόλια: Το Α2 το έχουμε δει εδώ http://mathematica.gr/forum/viewtopic.php?f=58&t=54479 και το Α4 ήταν το πρόβλημα 5 του διαγωνισμού.

#2

silouan έγραψε:Ξεκινάω να βάζω και τα θέματα της περσινής λίστας από την ΙΜΟ.

Α1. Για την ακολουθία των θετικών πραγματικών $a_1, a_2,\ldots$ ισχύει ότι: $\displaystyle a_{k+1}\geq\frac{ka_k}{a_k^2+k-1}$ για κάθε θετικό ακέραιο .
Να αποδείξετε ότι $a_1+a_2+\ldots+a_n\geq n$ για κάθε $n\geq 2$ .

Θα δείξω αρχικά ότι $\displaystyle{ a_1 + \cdots + a_n \geqslant \frac{n}{a_{n+1}}}$ για κάθε $n \geqslant 1$ .

Προχωράω επαγωγικά. Για n=1

ισχυρίζομαι ότι $a_1 \geqslant 1/a_2$ το οποίο είναι άμεσο από την δοσμένη συνθήκη για k=1

. Έστω λοιπόν επαγωγικά ότι

$\displaystyle{ a_1 + \cdots + a_r \geqslant \frac{r}{a_{r+1}} }$

Τότε

$\displaystyle{ a_1 + \cdots + a_r + a_{r+1} \geqslant \frac{r}{a_{r+1}} + a_{r+1} = \frac{a_{r+1}^2+r}{a_{r+1}} \geqslant \frac{r+1}{a_{r+2}} }$

όπου η τελευταία ανισότητα έπεται από την δοσμένη συνθήκη βάζοντας k = r+1

.

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

Πίσω τώρα στο ζητούμενο. Θα το αποδείξω και αυτό επαγωγικά. Για n=2

έχω

$\displaystyle{ a_1 + a_2 \geqslant a_1 + \frac{1}{a_1} \geqslant 2}$

οπότε το ζητούμενο ισχύει.

Έστω λοιπόν ότι το ζητούμενο ισχύει για n=r

. Δηλαδή $a_1 +\cdots + a_r \geqslant r$ .

Αν $a_{r+1} \geqslant 1$ τότε ασφαλώς είναι και $a_1 +\cdots + a_r + a_{r+1} \geqslant r + 1$ .
Αν $a_{r+1} \leqslant 1$ τότε $\displaystyle{a_1 +\cdots + a_r + a_{r+1} \geqslant \frac{r}{a_{r+1}} + a_{r + 1} = \frac{r-1}{a_{r+1}} + \left(\frac{1}{a_{r+1}} + a_{r+1} \right) \geqslant r-1 + 2 = r+1}$

Άρα το ζητούμενο ισχύει και για n=r+1

.

Οπότε επαγωγικά το ζητούμενο αποδείχθηκε.

#3

Demetres έγραψε: Θα δείξω αρχικά ότι $\displaystyle{ a_1 + \cdots + a_n \geqslant \frac{n}{a_{n+1}}}$ για κάθε $n \geqslant 1$ .

Δημήτρη, αυτό είναι το κλειδί για τη λύση της άσκησης. Η άσκηση είχε επιλεγεί να είναι το 5ο θέμα του περσινού διαγωνισμού, πριν διαρρεύσουν τα θέματα και αναγκαστούν να τα αλλάξουν.

Η προσέγγισή μου είναι παρόμοια, αλλά το πρώτο βήμα το κάνω αλλιώς. Αναποδογυρίζοντας (

) τη συνθήκη παίρνουμε
$\displaystyle a_k+\frac{k-1}{a_k}\geq\frac{k}{a_{k+1}}$ οπότε παίρνουμε την τηλεσκοπική σχέση:

$\displaystyle a_k\geq\frac{k}{a_{k+1}}-\frac{k-1}{a_k}$ . Και με πρόσθεση κατά μέλη παίρνουμε τη δική σου.

#4

Να συνεχίσουμε με τη συνδυαστική:

C1. Σε μία ευθεία υπάρχουν $n\geq 1$ πόλεις. Κάθε πόλη έχει μία αριστερή μπουλντόζα (στα αριστερά της πόλης και στραμμένη στα αριστερά) και μία δεξιά μπουλντόζα (στα δεξιά της πόλης και στραμμένη στα δεξιά). Όλες οι

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

και

με την

να είναι δεξιά της

. Θα λέμε ότι η πόλη

εξοβελίζει την πόλη

αν η δεξιά μπουλντόζα της

μπορεί να φτάσει στην πόλη

βγάζοντας από το δρόμο όλες τις μπουλντόζες που συναντά. Όμοια, θα λέμε ότι η πόλη

εξοβελίζει την πόλη

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

μπορεί να φτάσει στην πόλη

βγάζοντας από το δρόμο όλες τις μπουλντόζες που συναντά.
Να αποδείξετε ότι υπάρχει ακριβώς μία πόλη που δεν μπορεί να εξοβελιστεί από καμιά άλλη.

C2. Περσινό πρώτο θέμα της ΙΜΟ.

C3. Σε ένα πεπερασμένο σύνολο

με στοιχεία θετικούς ακέραιους, ονομάζουμε μία διαμέριση του

σε δύο μη κενά ξένα μεταξύ τους υποσύνολά του A_1, A_2

καλή, αν το ελάχιστο κοινό πολλαπλάσιο των στοιχείων του A_1

ισούται με το μέγιστο κοινό διαιρέτη των στοιχείων του A_2

. Να προσδιορίσετε την ελάχιστη τιμή του

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

θετικούς ακέραιους που έχει ακριβώς 2015

καλές διαμερίσεις.

C4. Έστω

ένας θετικός ακέραιος. Οι παίκτες

και

παίζουν εναλλάξ ένα παιχνίδι, διαλέγοντας κάθε φορά έναν θετικό ακέραιο $k\leq n$ .
Οι κανόνες είναι οι ακόλουθοι:
α) Ένας παίκτης δεν μπορεί να διαλέξει έναν αριθμό που ο ίδιος ή ο άλλος παίκτης έχει ήδη επιλέξει σε προηγούμενη κίνηση.
β) Ένας παίκτης δεν μπορεί να διαλέξει έναν αριθμό, διαδοχικό σε κάποιον που ο ίδιος έχει ήδη επιλέξει σε προηγούμενη κίνηση.
γ) Το παιχνίδι λήγει με ισοπαλία αν όλοι οι αριθμοί επιλεγούν. Αλλιώς, ο παίκτης που στην κίνησή του δεν μπορεί να επιλέξει κάποιον αριθμό, χάνει.

Αν ο παίκτης

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

C5. Περσινό 6ο θέμα της ΙΜΟ.

C6. Έστω

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

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

. Να αποδείξετε ότι υπάρχουν άπειροι θετικοί ακέραιοι που δεν είναι καθαροί.

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

ακοινώνητα γκρουπ, να αποδείξετε ότι είναι δυνατόν να διαμερίσουμε την εταιρία σε 11 μέρη, έτσι ώστε να μην υπάρχουν εχθροί στο ίδιο μέρος.

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

#5

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

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

Λέμε ότι μια μπουλντόζα είναι νικήτρια αν δεν εξοβελιστεί από καμία άλλη μπουλντόζα.

Ισχυρισμός 1: Μια πόλη

δεν εξοβελίζεται από καμία άλλη αν και μόνο αν και οι δύο μπουλντόζες της

είναι νικήτριες.

Απόδειξη:

Ας υποθέσουμε αρχικά ότι οι μπουλντόζες της

είναι νικήτριες. Αρχικά η πόλη

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

είναι νικήτριες. Άρα η

δεν εξοβελίζεται από καμία άλλη πόλη.

Για το αντίστροφο ας υποθέσουμε ότι τουλάχιστον μία μπουλντόζα της

δεν είναι νικήτρια. Τότε κάποια άλλη μπουλντόζα θα την βγάλει από τον δρόμο. Την στιγμή που θα βγει από τον δρόμο είτε κάποια άλλη μπουλντόζα έχει ήδη περάσει από την

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

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

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

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

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

είτε έχει κατεύθυνση προς την

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

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

αφού τότε αυτή η μπουλντόζα ακόμη δεν τερμάτισε. Άρα σίγουρα θα περάσει μια μπουλντόζα από την

. Οπότε ο ισχυρισμός έχει αποδειχθεί.

Ισχυρισμός 2: Υπάρχει το πολύ μία πόλη που δεν εξοβελίζεται από καμία άλλη.

Απόδειξη: Έστω ότι υπάρχουν δύο πόλεις, έστω η

και η

με την

αριστερά της

. Αν όμως η δεξιά μπουλντόζα της

είναι νικήτρια τότε σίγουρα θα πρέπει να περάσει από την πόλη

αφού σε αντίθετη περίπτωση θα έχει βγει από τον δρόμο. Άτοπο.

Ισχυρισμός 3: Υπάρχει τουλάχιστον μία πόλη που δεν εξοβελίζεται από άλλη.

Απόδειξη: Κατασκευάζω ένα κατευθυνόμενο γράφημα ως εξής: Ξεκινάω με κορυφές τις πόλεις $A_1,A_2,\ldots,A_n$ οι οποίες βρίσκονται με αυτήν την σειρά στην ευθεία. Επίσης έχω τις μη κατευθυνόμενες ακμές $A_1A_2,\ldots,A_{n-1}A_n$ .

Για κάθε

γνωρίζουμε ότι η πόλη A_i

εξοβελίζεται. Έστω ότι η τελευταία μπουλντόζα που πέρασε από την A_i

είχε ξεκινήσει από την A_j

. Αν

τότε κατευθύνω την ακμή $A_{i}A_{i+1}$ από το $A_{i+1}$ στο $A_{i}$ . Αν j < i

τότε κατευθύνω την ακμή $A_{i-1}A_{i}$ από το $A_{i-1}$ στο $A_{i}$ .

Έχουμε συνολικά n-1

ακμές στις οποίες βάλαμε

κατευθύνσεις. Άρα σε μία ακμή, έστω στην $A_iA_{i+1}$ έχουμε βάλει δύο κατευθύνσεις. Εκ κατασκευής δεν μπορεί να είναι και οι δύο προς την ίδια κατεύθυνση. Άρα πρέπει να είναι μία προς την A_i

και μία προς $A_{i+1}$ . Αλλά και αυτό είναι αδύνατο. Πράγματι αυτό σημαίνει πως υπάρχει j > i

ώστε η τελευταία μπουλντόζα που πέρασε από την A_i

ξεκίνησε από την A_j

. Ας την ονομάσω A_j^L

αφού είναι η αριστερή μπουλντόζα της A_j

. Επίσης υπάρχει k < i+1

ώστε η τελευταία μπουλντόζα που πέρασε από την $A_{i+1}$ ξεκίνησε από την A_k

. Ας την ονομάσω A_k^R

. Αυτές οι δύο μπουλντόζες σίγουρα συναντήθηκαν. Δεν μπορούν να συναντήθηκαν ενδιάμεσα των A_i

και $A_{i+1}$ αφού τότε αν π.χ. βγει από τον δρόμο η A_k^R

τότε δεν θα προλάβαινε να περάσει από την $A_{i+1}$ . Δεν μπορεί να συναντήθηκαν αριστερά της A_i

. Πράγματι τότε η μεν A_j^R

πέρασε από την A_i

. Η δε

ακόμη δε πέρασε από την $A_{i+1}$ . Για να περάσει όμως από την $A_{i+1}$ πρέπει πρώτα να περάσει από την A_i

. Τότε όμως θα περάσει από την A_i

μετά από την μπουλντόζα A_j^R

, άτοπο.

Οπότε και ο Ισχυρισμός 3 έχει αποδειχθεί και μαζί με τον Ισχυρισμό 2 αποδεικνύουν το ζητούμενο.

#6

Δημήτρη, ωραία!
Μπορούμε να το κάνουμε και λίγο διαφορετικά. Να ξεχάσουμε τις ακριανές μπουλντόζες (την τέρμα αριστερά και την τέρμα δεξιά) και για τις υπόλοιπες πόλεις να πάρουμε την μέγιστη μπουλντόζα και να πάμε επαγωγικά. Γίνεται ενδεχομένως λίγο συντομότερα έτσι.

Έκανα και μία αλλαγή στο C7 (ευχαριστώ το Γιώργο Βλάχο για την επισήμανση). Είχα γράψει εκ παραδρομής "τουλάχιστον" αντί "το πολύ"

#7

Βάζω και τα πρώτα τέσσερα θέματα Θεωρίας Αριθμών:

Ν1. Να προσδιορίσετε όλους τους θετικούς ακεραίους

για τους οποίους η ακολουθία που ορίζεται ως $a_0=\frac{2M+1}{2}$ και $a_{k+1}=a_k\lfloor a_k\rfloor$ περιέχει έναν τουλάχιστον όρο που είναι ακέραιος.

Ν2. Οι θετικοί ακέραιοι a,b

είναι τέτοιοι ώστε ο a!b!

είναι πολλαπλάσιο του a!+b!

.
Να αποδείξετε ότι $3a\geqslant 2b+2$ .

N3. Θεωρούμε τους θετικούς ακεραίους

και

με

. Ορίζουμε
$\displaystyle x_k=\frac{m+k}{n+k}$ για k=1,2,...,n+1

. Να αποδείξετε ότι αν όλοι οι αριθμοί $x_1,x_2,...,x_{n+1}$ είναι ακέραιοι, τότε ο $x_1x_2\cdots x_{n+1}-1$ έχει έναν τουλάχιστον περιττό πρώτο διαιρέτη.

Ν4. Οι ακολουθίες θετικών ακεραίων a_n

και

ορίζονται ως εξής:
$a_0,b_0\geqslant 2$ και $a_{n+1}=\gcd (a_n,b_n)+1$ και $b_{n+1}=\lcm (a_n, b_n)-1$ .
Nα αποδείξετε ότι η ακολουθία a_n

είναι τελικά περιοδική.

#8

silouan έγραψε: Ν1. Να προσδιορίσετε όλους τους θετικούς ακεραίους για τους οποίους η ακολουθία που ορίζεται ως $a_0=\frac{2M+1}{2}$ και $a_{k+1}=a_k\lfloor a_k\rfloor$ περιέχει έναν τουλάχιστον όρο που είναι ακέραιος.

Θα δείξουμε ότι για κάθε θετικό ακέραιο $M\geq 2$ υπάρχει ένας τουλάχιστον όρος της ακολουθίας που να είναι ακέραιος.

$\spadesuit$ Αρχικά αν M=1

τότε η ακολουθία είναι σταθερή και κάθε όρος είναι ίσος με $\dfrac{3}{2}$ . Άρα η τιμή M=1

απορρίπτεται.

$\spadesuit$ Επίσης αν ο

είναι άρτιος τότε $a_1=a_0\left[a_0\right]=\left(M+\dfrac{1}{2}\right)\cdot M\in\mathbb{Z}$ οπότε όλοι οι άρτιοι αριθμοί

είναι δεκτοί.

$\spadesuit$ Αν ο

είναι περιττός > 1

τότε γράφεται στη μορφή M=2^kt+1

με

περιττό. Θα δείξουμε ότι $a_{k+1}\in \mathbb{Z}$ .

$a_0=M+\dfrac{1}{2}=2\cdot \underbrace{2^{k-1}t}_{r_1}+1+\dfrac{1}{2} =2r_1+1+\dfrac{1}{2}$

$a_1=\left(2r_1+\dfrac{3}{2}\right)(2r_1+1)=\underbrace{4r_1^2+5r_1+1}_{2r_2+1}+\dfrac{1}{2}$ με $r_2=2r_1^2+5\dfrac{r_1}{2}$

$a_2=\left(2r_2+\dfrac{3}{2}\right)(2r_2+1)=\underbrace{4r_2^2+5r_2+1}_{2r_3+1}+\dfrac{1}{2}$ με $r_3=2r_2^2+5\dfrac{r_2}{2}$

$\vdots$

$a_{k-1}=\left(2r_{k-1}+\dfrac{3}{2}\right)(2r_{k-1}+1)=\underbrace{4r_{k-1}^2+5r_{k-1}+1}_{2r_k+1}+\dfrac{1}{2}$ με $r_k=2r_{k-1}^2+5\dfrac{r_{k-1}}{2}$

Φανερά τα r_i

για

έως

είναι όλα άρτιοι αριθμοί ενώ το r_k

είναι περιττός καθώς το $r_{k-1}$ περιέχει μόνο ένα

-άρι.

Έτσι $a_k=\left(2r_k+\dfrac{3}{2}\right)(2r_k+1)=\underbrace{4r_k^2+5r_k+1}_{\text{\gr άρτιος \en} = \ 2r}+\dfrac{1}{2}$

και τελικά $a_{k+1}=\left(2r+\dfrac{1}{2}\right)\cdot 2r\in\mathbb{Z}$ και η απόδειξη ολοκληρώθηκε.

Αλέξανδρος

Marios V. · #9

silouan έγραψε:Βάζω και τα πρώτα τέσσερα θέματα Θεωρίας Αριθμών:

Ν1. Να προσδιορίσετε όλους τους θετικούς ακεραίους για τους οποίους η ακολουθία που ορίζεται ως $a_0=\frac{2M+1}{2}$ και $a_{k+1}=a_k\lfloor a_k\rfloor$ περιέχει έναν τουλάχιστον όρο που είναι ακέραιος.

Ν2. Οι θετικοί ακέραιοι είναι τέτοιοι ώστε ο είναι πολλαπλάσιο του .
Να αποδείξετε ότι $3a\geqslant 2b+2$ .

N3. Θεωρούμε τους θετικούς ακεραίους και με . Ορίζουμε
$\displaystyle x_k=\frac{m+k}{n+k}$ για . Να αποδείξετε ότι αν όλοι οι αριθμοί $x_1,x_2,...,x_{n+1}$ είναι ακέραιοι, τότε ο $x_1x_2\cdots x_{n+1}-1$ έχει έναν τουλάχιστον περιττό πρώτο διαιρέτη.

Ν4. Οι ακολουθίες θετικών ακεραίων και ορίζονται ως εξής:
$a_0,b_0\geqslant 2$ και $a_{n+1}=\gcd (a_n,b_n)+1$ και $b_{n+1}=\lcm (a_n, b_n)-1$ .
Nα αποδείξετε ότι η ακολουθία είναι τελικά περιοδική.

Ευχαριστούμε Σιλουανέ!

Για το Πρώτο:

Αν M=1

έχουμε $a_0=\frac{3}{2}$ , $a_1=\frac{3}{2}\times 1=\frac{3}{2}$ και επαγωγικά η ακολουθία είναι σταθερή και πάντα μη- ακέραια.

Αν

άρτιο τότε $a_1=\frac{M(2M+1)}{2}$ ακέραιο και άρα όλα τα άρτια

είναι δεκτά.

Αν

περιττός με M>1

, τότε $M-1 \geq 1$ οπότε υπάρχουν θετικοί ακέραιοι p,x

με

και

περιττό. Να σημειωθεί ότι v_2(M-1)=p

.

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

Θα δείξω κατ' αρχάς ότι $a_n-\frac{1}{2}$ ακέραιος για κάθε μη-αρνητικό ακέραιο

(1). Δουλέυω επαγωγικά.

Πράγματι για n=0

, $a_0-\frac{1}{2}=M$ .

Υποθέτω πως ισχύει για n=k

όπου

κάποιος μη αρνητικός ακέραιος και θα δείξω πως ισχύει και για n=k+1

.
Είναι $a_{k+1}=a_k\lfloor a_k\rfloor=a_k(a_k-\frac{1}{2})$ .

Άρα ο $2a_{k+1}$ είναι ακέραιος. Εφόσον όμως ο $a_{k+1}$ δεν είναι, το $2a_{k+1}$ είναι περιττός και άρα $a_{κ+1}-\frac{1}{2}$ ακέραιος.

Επαγωγικά, ισχύει το (1).

Θέτω τώρα $b_n=a_n-\frac{3}{2}$ για κάθε μη-αρνητικό ακέραιο

.
Οι όροι αυτής της ακολουθίας είναι ακέραιοι, από το (1).
Να σημειωθεί επίσης πως $\lfloor a_{n}\rfloor=a_n(a_n-\frac{1}{2})$ για κάθε όρο της αρχικής ακολουθίας.

Η αναδρομική μας γράφεται επομένως ως: $b_{n+1}=\frac{b_n(2b_n+5)}{2}$ για κάθε μη-αρνητικό ακέραιο n δίνοντας:
$v_2(b_{n+1})=v_2(b_n)-1$ για κάθε

.

Έτσι, $v_2(b_{p})=v_2(b_{p-1})-1=...=v_2(b_{0})-p=0$ .
Άρα $b_{p}=a_p-\frac{3}{2}$ περιττό, άρα $a_p-\frac{1}{2}$ άρτιο δίνοντας έτσι ακέραιο $a_{p+1}$ , άτοπο.

Επομένως:

Υπάρχει τουλάχιστον ένας ακέραιος όρος της ακολουθίας αν και μόνο αν M>1

.

Για το Δεύτερο:

Κατ' αρχάς αν b=1

τότε

, άτοπο. Όμοια αν b=1

.

Επομένως μπορούμε να υποθέσουμε πως a,b>1

.

Αν $a \geq b$ έχουμε $3a \geq 3b \geq 2b+2$ , οπότε ισχύει έτσι κ' αλλιώς το ζητούμενο.

Αν a<b

, Η δεδομένη διαιρετότητα γράφεται ισοδύναμα : $1+\frac{b!}{a!}|b!$ ή ακόμα $1+\frac{b!}{a!}|(a!(1+\frac{b!}{a!})-b!=a!$ .

Θέτω b=a+k

, άρα η προηγούμενη γίνεαι 1+(a+1) ...(a+k)|a!

και η ζητούμενη σχέση γράφεται ισοδύναμα $a \geq 2k+2$ .

Υποθέτω τώρα πως υπάρχουν θετικοί ακέραιοι a,k

με

και

, έχοντας ως σκοπό να καταλήξω σε άτοπο.

Αν $k \geq a$ έχουμε $(a+1)...(a+k) \geq a^a \geq a!$ επομένως 1+(a+1)...(a+k)>a!

άτοπο.

Είναι λοιπόν k<a<2k+2

και άρα $k+1 \leq a \leq 2k+1$ .

Έστω τώρα

πρώτος διαιρέτης της παράστασης 1+(a+1)...(a+k)

. Αν είναι p|k!

τότε

επειδή

, άτοπο.
Είναι όμως p|a!

και άρα $k<p \leq a \leq 2k+1$ . Επομένως $k+1 \leq p \leq 2k+1$ και άρα 2p>a

επομένως το p^2

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

. Άρα, δεν διαιρεί ούτε και το 1+(a+1)...(a+k)

.

Το τελευταίο επομένως μπορεί να γραφτεί ως γινόμενο διακριτών πρώτων στο διάστημα [k+1,2k+1]

.
Αν έστω και ένας ακέραιος σε αυτό το διάστημα δεν είναι πρώτος τότε $1+(a+1)...(a+k) \leq (k+1+1)...(k+1+k)$ , άτοπο αφού από $a \leq k+1$ έχουμε $1+(a+1)...(a+k) > (a+1)...(a+k) \geq (k+1+1)...(k+1+k)$ .

Αν τώρα όλοι οι ακέραιοι του διαστήματος είναι πρώτοι, τότε k<2

αφού δεν υπάρχουν

διαδοχικοί αριθμοί που να είναι πρώτοι. Οπότε k=1

που δίνει $2 \leq a \leq 3$ . Πέρνουμε λοιπόν a=2

ή

που και τα δυο απορρίπτονται.

Ισχύει επομένως το ζητούμενο.

(μιας και πρόλαβα να γράψω λύση για το πρώτο την αφήνω αν και είναι παρόμοια με την προηγούμενη)

#10

Ευχαριστώ για την ενασχόληση!
Έγινε μια αλλαγή στο C4.
Ευχαριστώ το Δημήτρη για την υπόδειξη

ksofsa · #11

Για την τρίτη θεωρία αριθμών:

Εχω $x_{k}=\frac{a}{n+k}+1,a=m-n$ .

Οπότε αρκεί ν.δ.ό. $A=(\frac{a}{n+1}+1)...(\frac{a}{2n+1}+1)$ δε γράφεται στη μορφή $2^{b}+1$ .

Προφανώς lcm(n+1,...,2n+1)/a

.

Αρα $a=2^{c}dlcm(n+1,...,2n+1),c\geq 0$ και

περιττός.

Αν d>1

,τότε θεωρώ p πρώτο διαιρέτη του

.

Τότε

Αρα

.

Εύκολα αποδεικνύεται ότι μεταξύ των αριθμών n+1,...,2n+1

υπάρχει ένας

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

Εστω $r=2^{t}q$ .

Αν $c=0,\frac{a}{r}+1=0(mod2)$ ,οπότε A δε γράφεται στη μορφή $2^{b}+1$ .

Αρα $c\geq 1$ .

Τότε, $\frac{a}{x}=o(mod2^{c+1})A,x\epsilon (n+1,...,2n+1)-\left\{r \right\}$ .

ενώ $\frac{a}{r}\neq 0(mod2^{c+1})$

Αρα $A\neq 1(mod2^{c+1}$

Εστω $A=2^{b}+1$ .Επειδή b>>c+1

,πρέπει $A=1(mod2^{c+1})$ ,άτοπο και η απόδειξη ολοκληρώθηκε.

Πείτε μου ,σας παρακαλώ, αν υπάρχει λάθος.

#12

silouan έγραψε: C4. Έστω ένας θετικός ακέραιος. Οι παίκτες και παίζουν εναλλάξ ένα παιχνίδι, διαλέγοντας κάθε φορά έναν θετικό ακέραιο $k\leq n$ .
Οι κανόνες είναι οι ακόλουθοι:
α) Ένας παίκτης δεν μπορεί να διαλέξει έναν αριθμό που ο ίδιος ή ο άλλος παίκτης έχει ήδη επιλέξει σε προηγούμενη κίνηση.
β) Ένας παίκτης δεν μπορεί να διαλέξει έναν αριθμό, διαδοχικό σε κάποιον που ο ίδιος έχει ήδη επιλέξει σε προηγούμενη κίνηση.
γ) Το παιχνίδι λήγει με ισοπαλία αν όλοι οι αριθμοί επιλεγούν. Αλλιώς, ο παίκτης που στην κίνησή του δεν μπορεί να επιλέξει κάποιον αριθμό, χάνει.

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

Είναι εύκολο να δούμε ότι το παιγνίδι για n=1,2

είναι ισοπαλία.

Για τα υπόλοιπα

θα δείξω ότι το παιγνίδι είναι ισοπαλία για

άρτιο και νίκη του

για

περιττό. [Αυτό είναι λάθος. Δείτε πιο κάτω]

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

(για

).

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

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

μπορεί να επιλέξει οποιονδήποτε από τους αριθμούς της ομάδας εκτός από τον ένα ακριανό ενώ ο

οποιονδήποτε από τους αριθμούς της ομάδας εκτός από τον άλλο ακριανό.
2) Ο

μπορεί να επιλέξει οποιονδήποτε από τους αριθμούς της ομάδας εκτός από τον ένα ακριανό ενώ ο

οποιονδήποτε.
3) Ο

μπορεί να επιλέξει οποιονδήποτε από τους αριθμούς της ομάδας εκτός από τους δύο ακριανούς ενώ ο

οποιονδήποτε. [Εδώ επιτρέπω οι δυο ακριανοί να ταυτίζονται.]
Επιπλέον υπάρχει τουλάχιστον μια ομάδα της μορφής (2) ή (3).

Απόδειξη: Αυτό ισχύει σίγουρα μετά την πρώτη κίνηση του

αφού είτε θα έχω είτε μία είτε δύο ομάδες της μορφής (2). [Ανάλογα με το αν ο

αρχικά παίξει στην άκρη ή όχι.] Ο

στην κίνησή του επιλέγει μια ομάδα της μορφής (2) ή (3) και διαλέγει έναν αριθμό από την άκρη της. Αν η ομάδα είναι της μορφής (2) τότε επιλέγει την άκρη που θα μπορούσε να επιλέξει και ο

. Έτσι μετατρέπει αυτήν την ομάδα σε ομάδα της μορφής (1). Αν ο

παίξει σε ομάδα οποιασδήποτε μορφής θα δημιουργήσει σίγουρα μια ομάδα της μορφής (2) ή (3) και ίσως ακόμη μία ομάδα της μορφής (1) ή (2) ή (3). Οπότε ο ισχυρισμός αποδείχθηκε.

Είναι φανερό τώρα ότι ο

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

Επιστρέφουμε τώρα στο παιγνίδι με την συνθήκη (γ). Αν n > 2

περιττός τότε ο

κερδίζει αφού ακολουθώντας την προηγούμενη τακτική. Πράγματι ο

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

Μέχρι εδώ όλα καλά. Η επόμενη παράγραφος είναι λανθασμένη. Θα επανέλθω με την διόρθωση σε νέα ανάρτηση.

Θα δείξουμε τώρα ότι ο

μπορεί να φέρει ισοπαλία αν n > 2

άρτιος. Αρχικά ξεκινάει επιλέγοντας τον

. Ας υποθέσουμε πως ο

επιλέγει τον k > 1

. Τότε η ομάδα των αριθμών $1,2,\ldots,k-1$ είναι της μορφής (2) και η ομάδα $k+1,\ldots,n-1$ της μορφής (1) αν εναλλάξουμε τους ρόλους των

και

. Άρα αν ο

ακολουθήσει την πιο πάνω στρατηγική θα κερδίσει χωρίς την συνθήκη (γ) και άρα δεν θα χάσει με την συνθήκη (γ). Ο

λοιπόν αναγκάζεται να παίξει στην θέση

. Τότε ο

παίζει στην θέση

και ο

αναγκάζεται να παίξει στην θέση n-1

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

#13

silouan έγραψε: C4. Έστω ένας θετικός ακέραιος. Οι παίκτες και παίζουν εναλλάξ ένα παιχνίδι, διαλέγοντας κάθε φορά έναν θετικό ακέραιο $k\leq n$ .
Οι κανόνες είναι οι ακόλουθοι:
α) Ένας παίκτης δεν μπορεί να διαλέξει έναν αριθμό που ο ίδιος ή ο άλλος παίκτης έχει ήδη επιλέξει σε προηγούμενη κίνηση.
β) Ένας παίκτης δεν μπορεί να διαλέξει έναν αριθμό, διαδοχικό σε κάποιον που ο ίδιος έχει ήδη επιλέξει σε προηγούμενη κίνηση.
γ) Το παιχνίδι λήγει με ισοπαλία αν όλοι οι αριθμοί επιλεγούν. Αλλιώς, ο παίκτης που στην κίνησή του δεν μπορεί να επιλέξει κάποιον αριθμό, χάνει.

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

Για δείτε και εδώ.

Ουσιαστικά αν αφαιρέσουμε την συνθήκη (γ) είναι το παιγνίδι COL στο γράφημα P_n

. Στην σελίδα 95 υπάρχει η απάντηση ότι σε αυτό το παιγνίδι για $n \geqslant 2$ κερδίζει ο δεύτερος παίκτης. [Χρειάζεται όμως κάποια αποκρυπτογράφηση.]

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

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

Πριν μερικά χρόνια μπήκε ένα πρόβλημα στην ΙΜΟ που μας έκανε να ασχοληθούμε με πιθανολογικές μεθόδους. Τώρα θα αρχίσουμε να ασχολούμαστε με Surreal Numbers. (Δεν χρειάζονται για το συγκεκριμένο πρόβλημα αλλά υποβόσκουν.)

dement · #14

silouan έγραψε: Ν4. Οι ακολουθίες θετικών ακεραίων και ορίζονται ως εξής:
$a_0,b_0\geqslant 2$ και $a_{n+1}=\gcd (a_n,b_n)+1$ και $b_{n+1}=\lcm (a_n, b_n)-1$ .
Nα αποδείξετε ότι η ακολουθία είναι τελικά περιοδική.

Αν $a_n \mid b_n$ τότε $a_{n+1} = a_n + 1, b_{n+1} = b_n - 1$ , αλλιώς $a_{n+1} = \gcd (a_n, b_n) + 1 \leq a_n$ . Ονομάζουμε κορυφές τα σημεία $p_k \in \mathbb{N}$ με $a_{p_k} \nmid b_{p_k}$ . Για $p_k < m \leq p_{k+1}$ ισχύει $a_m + b_m = a_{p_{k+1}} + b_{p_{k+1}} \equiv s_{k+1}$ . Παρατηρούμε ότι:

1. Η υπακολουθία $(a_{p_n})$ είναι φθίνουσα.

Πράγματι, έστω κορυφή $a_{p_k}$ . Τότε $a_{p_k+1} = \gcd (a_{p_k}, b_{p_k}) + 1, b_{p_k+1} = \lcm (a_{p_k}, b_{p_k}) - 1$ . Προφανώς $a_{p_k} \nmid \gcd (a_{p_k}, b_{p_k}) + \lcm (a_{p_k}, b_{p_k}) = s_{k+1}$ , οπότε $a_{p_k} \nmid s_{k+1} - a_{p_k}$ , άρα $a_{p_{k+1}} \leq a_{p_k}$ .

2. Αν $a_{p_k} = a_{p_{k+1}}$ τότε $a_{p_k+1} = a_{p_{k+1}+1}$ .

Πράγματι, σε αυτή την περίπτωση ισχύει

$b_{p_{k+1}} = s_{k+1} - a_{p_{k+1}} = \gcd (a_{p_k}, b_{p_k}) + \lcm (a_{p_k}, b_{p_k}) - a_{p_k}$ .

Βλέπουμε ότι ο $\gcd (a_{p_k}, b_{p_k})$ είναι ΜΚΔ των $a_{p_{k+1}} = a_{p_k}$ και $b_{p_{k+1}}$ οπότε $a_{p_k+1} = a_{p_{k+1}+1} = \gcd (a_{p_k}, b_{p_k}) + 1$ .

Από τις δύο παρατηρήσεις έπεται το ζητούμενο για

αρκετά μεγάλο ώστε $\displaystyle a_{p_n} = \inf_{k \in \mathbb{N}} a_{p_k}$ .

#15

Επανέρχομαι για την C4:

Έχω μέχρι στιγμής δείξει ότι το παιγνίδι είναι ισοπαλία για n=1,2

και ότι ο

κερδίζει για

περιττό.

Για τα υπόλοιπα

θα δείξω ότι είναι ισοπαλία για n=4,6

, αλλιώς κερδίζει ο

.

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

1) Ο

μπορεί να επιλέξει οποιονδήποτε από τους αριθμούς της ομάδας εκτός από τον ένα ακριανό ενώ ο

οποιονδήποτε από τους αριθμούς της ομάδας εκτός από τον άλλο ακριανό.
2) Ο

μπορεί να επιλέξει οποιονδήποτε από τους αριθμούς της ομάδας εκτός από τον ένα ακριανό ενώ ο

οποιονδήποτε.
3) Ο

μπορεί να επιλέξει οποιονδήποτε από τους αριθμούς της ομάδας εκτός από τους δύο ακριανούς ενώ ο

οποιονδήποτε. [Εδώ επιτρέπω οι δυο ακριανοί να ταυτίζονται.]
4) Ο

μπορεί να επιλέξει οποιονδήποτε από τους αριθμούς της ομάδας εκτός από τον ένα ακριανό ενώ ο

οποιονδήποτε.
5) Ο

μπορεί να επιλέξει οποιονδήποτε από τους αριθμούς της ομάδας εκτός από τους δύο ακριανούς ενώ ο

οποιονδήποτε. [Εδώ επιτρέπω οι δυο ακριανοί να ταυτίζονται.]

Για n=4

ο

αρχίζει επιλέγοντας τον

. Αν ο

επιλέξει τον

τότε ο

επιλέγει τον

και κερδίζει. Αν ο

επιλέγει τον

ο

επιλέγει τον

και κερδίζει. Άρα ο

για να μην χάσει πρέπει να επιλέξει τον

. Τότε ο

αναγκαστικά επιλέγει τον

και μετά ο

αναγκαστικά τον

οπότε έχουμε ισοπαλία.

Για n=6

ο

αρχίζει επιλέγοντας τον

. Αν ο

επιλέξει οποιονδήποτε άλλον εκτός από τον

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

μπορεί να παίξει τελευταίος και άρα να κερδίζει. Αν ο

επιλέξει τον

τότε ο

επιλέγει τον

. Ο

μπορεί να επιλέξει οποιονδήποτε από τους 3,5

. Οπότε ο

μπορεί να επιλέξει τον

και μετά ο

αναγκαστικά τον άλλο από τους 3,5

. Άρα έχουμε ισοπαλία.

Έστω τώρα $n \geqslant 6$ άρτιος. Θα δείξω ότι κερδίζει ο

.

Ξεκινάει να παίζει ο

. Αν επιλέξει ακριανό αριθμό θα έχουμε μια ομάδα της μορφής (2) ενώ αν επιλέξει μεσαίο αριθμό θα έχουμε δύο ομάδες της μορφής (2) ή μία της (2) και μία της (3). [Το τελευταίο μπορεί να συμβεί αν π.χ. ο

επιλέξει τον k=2

.] Στην περίπτωση λοιπόν που ο

επιλέξει μεσαίο ο

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

θα υπάρχουν τουλάχιστον δύο ομάδες της μορφής (2) ή (3) και καμία των (4),(5). Άρα όχι μόνο θα μπορεί να παίζει πάντα ο

αλλά όταν δεν μπορεί να παίξει ο

, ο

θα έχει επιπλέον κίνηση. Άρα σίγουρα κερδίζει ο

.

Χωρίς βλάβη της γενικότητας λοιπόν ο

επιλέγει τον

και δημιουργεί μια ομάδα της μορφής (2). Τότε ο

επιλέγει τον

.
- Αν ο

επιλέξει τον

τότε ο

επιλέγει τον

και αφήνει μια ομάδα της μορφής (1). Οπότε ο

με την προηγούμενη τακτική μπορεί να παίξει τελευταίος. Επιπλέον κανείς δεν θα επιλέξει τον

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

.
- Αν ο

επιλέξει τον

τότε έχουμε μια ομάδα της μορφής (3) και είναι η σειρά του

να παίξει. Ακολουθώντας την προηγούμενη τακτική μπορεί να παίξει τελευταίος. Επιπλέον κανείς δεν μπορεί να επιλέξει τον

και άρα δεν έχουμε ισοπαλία. Άρα πάλι κερδίζει ο

.
- Αν ο

επιλέξει τον

με $4 \leqslant k \leqslant n-3$ τότε ο

επιλέγει τον k+2

και δημιουργεί δύο ομάδες της μορφής (1). [Μία αν k = n-3

.] Οπότε ο

ακολουθώντας την προηγούμενη τακτική μπορεί να παίξει τελευταίος. Επιπλέον κανείς δεν μπορεί να επιλέξει τον k+1

και άρα δεν έχουμε ισοπαλία. Άρα πάλι κερδίζει ο

.
- Αν ο

επιλέξει τον n-2

τότε ο

επιλέγει τον

. Τότε παραμείνει μια ομάδα αποτελούμενη από τους 2,3

της μορφής (5), μία αποτελούμενη από τον n-1

της μορφής (3) και πιθανώς μία άλλη αποτελούμενη από τους $5,6,\ldots,n-3$ της μορφής (1). [Αν n=8

η τελευταία ομάδα δεν υπάρχει.] Ο

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

επιλέξει ένας από τους

ή

. Τότε ο

επιλέγει τον n-1

. Έτσι μπορεί να παίξει τελευταίος. [Όταν ο

επιλέξει έναν από τους

ή

αυτομάτως δεν μπορεί να επιλέξει τον άλλο.] Επειδή δεν μπορεί να υπάρχει ισοπαλία, (ένας από τους 2,3

δεν θα επιλεγεί) ο

κερδίζει.

#16

Κλείνω τη λίστα με τα υπόλοιπα προβλήματα της θεωρίας αριθμών.
Εδώ δυσκολεύουν λίγο τα πράγματα αλλά ελπίζω να δούμε λύσεις!

Ν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(k)-k

είναι περιοδική.

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

φορές με τον εαυτό της.

Ν7. Για κάθε θετικό ακέραιο

μία συνάρτηση $f:\mathbb{Z}_{>0}\rightarrow\mathbb{Z}_{>0}$ θα λέγεται

-καλή αν $\displaystyle\gcd (f(m)+n, f(n)+m)\leqslant k$ για κάθε $m\neq n$ . Να βρεθούν όλα τα

για τα οποία υπάρχει

-καλή συνάρτηση.

Ν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)$

GVlachos · #17

Σιλουανέ σε ευχαριστούμε, για άλλη μια χρονιά, για τα προβλήματα.

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

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

Λήμμα 1: Σε οποιαδήποτε καλή διαμέριση, κάθε στοιχείο του A_1

είναι μικρότερο από κάθε στοιχείο του A_2

.

Αν

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

καλές διαμερίσεις, θα δείξουμε ότι f(1)=3, f(n+2)=f(n)+3

που δίνει

.

-

προκύπτει από το σύνολο $\{2,3,6\}$ .

- $f(n+2)\leq f(n)+3$
Έστω A^n

σύνολο

στοιχείων με ακριβώς

καλές διαμερίσεις,

το lcm των στοιχείων του και p,q>L

πρώτοι αριθμοί. Το σύνολο $A^n\cup \{pL,qL,pqL\}$ έχει τις 2 επιπλέον διαμερίσεις $\{A^n\}|\{pL,qL,pqL\}$ και $\{A^n\cup \{pL,qL\}\}| \{pqL\}$

- $f(n+2)\geq f(n)+3$
Έστω $A^{n+2}$ με f(n+2)

στοιχεία όπως ορίστηκε παραπάνω και έστω $f(n+2)\leq f(n)+2$ . Αν αφαιρέσουμε από το σύνολο τα 2 μεγαλύτερα στοιχεία του k<l

, το καινούργιο σύνολο

έχει το πολύ

καλές διαμερίσεις. Όμως τότε πρέπει και οι $\{A'\}|\{k,l\}, \{A'\cup \{k\}\}|\{l\}$ να είναι καλές διαμερίσεις. Έτσι εύκολα προκύπτει ότι $l=lcm(\{A'\cup \{k\})=k$ , άτοπο.

GVlachos · #18

silouan έγραψε: C6. Έστω ένα μη κενό σύνολο που αποτελείται από θετικούς ακεραίους. Θα λέμε ότι ένας θετικός ακέραιος είναι καθαρός, αν έχει μοναδική αναπαράσταση σαν άθροισμα από περιττό πλήθος διακεκριμένων στοιχείων του . Να αποδείξετε ότι υπάρχουν άπειροι θετικοί ακέραιοι που δεν είναι καθαροί.

'Εστω ότι όλοι οι ακέραιοι μεγαλύτεροι ή ίσοι κάποιου k>100

είναι καθαροί.
$s_1<s_2<\cdots<s_n<\cdots$ τα στοιχεία του

και

ο ελάχιστος δείκτης για τον οποίο s_z>k

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

.

Ξεκινάω με τα βήματα της απόδειξης. Η απόδειξη για κάθε βήμα ακολουθεί από κάτω:
1) Για k < x < y

ισχύει $y \geq 2x-k$
2) $S_{i=1}^{j-1}s_i < s_j+k log(s_j)$ .
3) Υπάρχει σταθερά

ώστε κάθε

να γράγεται με μοναδικό τρόπο ως άθροισμα άρτιου το πλήθος στοιχείων του

.
4) Έστω K=max(k,k')

και

ο ελάχιστος δείκτης για τον οποίο s_Z>K

. Τότε $S_{i=z}^{j-1}s_i < s_j$ για j>Z

.
5) Υπάρχει L>K

ώστε για κάθε s_j>L

, $\sum_{i=1}^{j-1}s_i<2s_j$ .
6) Θέτουμε $S'=\{s|s\in S,s>L\}$ . Αντιστοιχούμε κάθε πεπερασμένο υποσύνολο του

σε ένα δυαδικό αριθμό. Αν το υποσύνολο περιέχει το

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

, τότε ο δυαδικός αριθμός έχει μονάδα στη θέση

, αλλιώς

. Για παράδειγμα ο αριθμός 1011 αντιστοιχεί στο σύνολο που περιέχει τα

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

και το

ο μικρότερο.
7) Από κάθε

πεπερασμένα υποσύνολα του

, το υποσύνολο με το μεγαλύτερο άθροισμα στοιχείων είναι αυτό που αντιστοιχεί στο μεγαλύτερο δυαδικό αριθμό. Θα γράφουμε [δυαδική αναπαράσταση] για το άθροισμα των στοιχείων του συνόλο. Δηλαδή για το σύνολο που αντοιστοιχεί στο 1011 θα γράφαμε [1011]
8) Αν [1000]<[111]+[1]

τότε το

γράγεται με

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

, οπότε καταλήγουμε σε άτοπο (2 περιττοί ή 2 άρτιοι τρόποι).
9) Αν [1000]>[111]+[1]

τότε το

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

, οπότε πάλι καταλήγουμε σε άτοπο(μόνo περιττός ή μόνο άρτιος τρόπος).
10) Έστω [1000]=[111]+[1]

. Γνωρίζουμε ότι το [1]

γράφεται σαν άρτιο άθροισμα αριθμών μικρότερων του [1]. Άρα το [111]

συν αυτό το άρτιο άθροισμα δίνουν μία περιττή αναπαράσταση του [1000]

, οπότε το [1000]

έχει 2 περιττές αναπαραστάσεις. Άτοπο.

Απόδειξη βημάτων:

1) Έστω $y \geq 2x-k-1$ . Τότε ο αριθμός 2x-1

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

και την περιττή αναπαράσταση του $2x-1-y \geq k$ . Επίσης ο αριθμός 2x-1

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

, δηλαδή την αναπαράσταση που περιέχει το

κααι την περιττή αναπαράσταση του x-1

. Επιλέγουμε $w>y,w\in S$ και το w+2k-1

έχει 2 περιττές αναπαραστάσεις. Άτοπο.

2) Από το (1), $s_{j-1} \leq s_j/2+k/2 < s_j/2+k$ και με επαγωγή $s_i \leq s_{i+1}/2+k/2 < (s_j/2^{j-i-1}+k)/2+k/2 < s_j/2^{j-i}+k$ και το ζητούμενο έπεται από απλή άλγεβρα.

3) Από το (1) $s_{i+1} \geq 2s_i-k \Leftrightarrow (s_{i+1}-k)\geq 2(s_i-k) \rightarrow \lim_{i\to\infty} \frac{s_i}{log(s_i)} = 0$ . 'Αρα υπάρχει

ώστε $\forall i>W$ να ισχύει $\sum_{j=1}^{i-1}s_j < s_i(1+\frac{1}{100})$ και $s_{i}(2-\frac{1}{100})<s_{i+1}$ . Άρα κάθε αριθμός

στο διάστημα $[s_i(1+\frac{1}{100}), s_i(2-\frac{1}{100})]$ για i>W

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

και μία (μοναδική) άρτια αναπαράσταση του x-s_i

. Άρα κάθε ακέραιος στο $[s_i(1+\frac{1}{100}), s_i(2-\frac{1}{100})]$ για i>W

έχει μοναδική άρτια αναπαράσταση. Τετριμμένα υπάρχει

ώστε κάθε ακέραιος στο $[k',+\infty]$ να ανήκει σε κάποιο $[s_i(1+\frac{1}{100}), s_i(2-\frac{1}{100})]$ και το ζητούμενο έπεται.

4) Θα δείξουμε ότι η άρτια αναπαράσταση του s_j

περιέχει όλα τα s_i

για $i\in [z,j-1]$ , που δίνει άμεσα το ζητούμενο. Έστω s_q

με $q\in [z,j-1]$ ελάχιστο που δεν περιέχεται στην άρτια αναπαράσταση του s_j

. Το

έχει μιά άρτια αναπαράσταση. Τότε s_q

συν την άρτια αναπαράσταση του s_j

είναι ίσο με s_j

συν την άρτια ανα παράσταση του s_q

και το

έχει 2 άρτιες αναπαραστάσεις. Άτοπο.

5) Προκύπτει άμεσα από το (4).

6) Είναι ορισμός, δεν θέλει απόδειξη.

7) Αν αφαιρέσουμε τα κοινά στοιχεία από τα 2 σύνολα, τότε το σύνολο με τη μεγαλύτερη δυαδική αναπαράσταση έχει το μεγαλύτερο στοιχείο, άρα και το μεγαλύτερο άθροισμα λόγω του (4).

8) Έστω [1000]<[111]+[1]

.
An

, τότε το

έχει 2 αναπαραστάσει από στοιχεία του

μικρότερα του [1]

. Άρα το

έχει 2 αναπαραστάσεις με στοιχεία μικρότερα του [1000]

και την τρίτη αναπαράσταση [1000]

. Άτοπο.
An $[1000]-[111]\leq K$ , τότε $[1000]-[110]\leq [1] + K$ και το

έχει 2 αναπαραστάσεις από στοιχεία του

μικρότερα του [10]

(επειδή

). Άρα το

έχει 2 αναπαραστάσεις με στοιχεία μικρότερα του [1000]

και την τρίτη αναπαράσταση [1000]

. Άτοπο.

9) Αν [1000]>[111]+[1]

τότε το

σε οποιαδήποτε αναπαράστασή του πρέπει να χρησιμοποιέι το [111]

, αφού από το (5) παίρνουμε $[110]+\sum_{s_j \in S, s_j<[1]}s_j<[111]+[1]$ . Άρα κάθε αναπαράσταση του

αποτελείται από τα [100],[10],[1]

και μία αναπαράσταση του [1]

. Το

έχει ακριβώς 2 αναπαραστάσεις, μία από τις οποίες είναι η [1]

. Επειδή μία αναπαράσταση δεν μπορεί να περιέχει το [1]

2 φορές, μένει μία μόνο αναπαράσταση για το [111]+[1]

. Άτοπο.

10) Η απόδειξη έγινε στην περιγραφή του βήματος.

GVlachos · #19

silouan έγραψε: Ν7. Για κάθε θετικό ακέραιο μία συνάρτηση $f:\mathbb{Z}_{>0}\rightarrow\mathbb{Z}_{>0}$ θα λέγεται -καλή αν $\displaystyle\gcd (f(m)+n, f(n)+m)\leqslant k$ για κάθε $m\neq n$ . Να βρεθούν όλα τα για τα οποία υπάρχει -καλή συνάρτηση.

Θα δείξουμε ότι υπάρχει τέτοια συνάρτηση k = 2

, οπότε υπάρχει και για κάθε $k\geq 2$ .

Λήμμα 1:
Το $x|\gcd (f(m)+n, f(n)+m)$ είναι ισοδύναμο με το να ισχύουν ταυτόχρονα οι 2 συνθήκες: $f(m)-m\equiv f(n)-n \equiv r (mod x)$ και $m+n+r \equiv 0 (mod x)$

Λήμμα 2:
Για κάθε $x \geq 3$ υπάρχει συνάρτηση $g_x:\mathbb{Z}_{>0}\rightarrow\mathbb{Z}_x$ ώστε $x \nmid \gcd (g(m)+n, g(n)+m), \forall m,n \in \mathbb{Z}_{>0}$ . Μια τέτοια συνάρτηση θα λέγεται

-καλή.
Απόδειξη:
Για n(mod x)<x/2

, θέτουμε

. Αν

τότε

Για

, θέτουμε

. Αν

τότε

Για

, θέτουμε

. Αν

τότε

Λήμμα 3:
Για κάθε $x \geq 100$ και συνάρτηση $f:\{1,2,..,x'\}\to Z_x$ (με $x' \leq \frac{x}{20}$ ) που ικανοποιεί $x \nmid \gcd (f(m)+n, f(n)+m)$ $\forall m\neq n \in \{1,2,..,x'\}$ , υπάρχει

-καλή συνάρτηση $f_x:\mathbb{Z}_{>0}\rightarrow\mathbb{Z}_x$ που οι τιμές τις συμπίπτουν με την

στο πεδίο ορισμού της

.
Απόδειξη:
Για $n \leq x'$ θέτουμε f_x(n)=f(n)

.
Για

, θέτουμε

, με

που δεν ανήκει στο σύνολο τιμών της

. Αν

τότε

Για $4x/10 \leq n (mod x) \leq 8x/10$ , θέτουμε g(n)-n=d (mod x)

με

που δεν ανήκει στο σύνολο τιμών της

. Αν $4x/10 \leq n,m (mod x) \leq 8x/10$ τότε 11x/10< (n+m+d) (mod x) (mod x) < 1.98x

Για

, θέτουμε

με

που δεν ανήκει στο σύνολο τιμών της

. Αν

τότε

Θα κατασκευάσουμε επαγωγικά την

που είναι

-καλή.
Ξεκινάμε με $f(1) \equiv g_x(1) (modx)$ για κάθε πρώτο x <100

και για

. Επίσης θέλουμε οι 10 επόμενοι ακέραιοι μετά το f(1)

να είναι σύνθετοι. Μπορούμε να επιλέξουμε τέτοιο f(1)

από το CRT (Chinese Remainder Theorem).
Επίσης ορίζουμε το σύνολο S_1

που περιέχει ακριβώς τους πρώτους αριθμούς μικρότερους του 100

και το

.
Έχουμε το base case της επαγωγής. Για i>1

ορίζουμε επαγωγικά το f(i)

ως εξής:
$S_i=S_1\cup\{$ σύνολο πρώτων μικρότερων του $10f(i-1)\}$ .
$f(i) \equiv g_x(i) (mod x), \forall x \in S_1$ ( g_x

όπως στο Λήμμα 2)
$f(i) \equiv f_x(i) (mod x), \forall x\in S_i/S_1$ ( f_x

όπως στο Λήμμα 3)
Οι 10^i

διαδοχικοί ακέραιοι μετά το f(i)

είναι σύνθετοι και f(i)>10f(i-1)

.
Το

με τις παραπάνω ιδιότητες υπάρχει από το CRT.

Απόδειξη ότι η

είναι 2-καλή:
Για $x\in S_1$ , $f(i) \equiv g_x(i) (mod x)$ , οπότε $x \nmid \displaystyle\gcd (f(m)+n, f(n)+m), \forall m>n>0$ .
Για $x\in S_i/S_{i-1}$ , αρκεί να δείξουμε ότι $x \nmid \displaystyle\gcd (f(m)+n, f(n)+m) \forall i-1\geqm>n>0$ , αφού τότε $f \equiv f_x (mod x)$ για κάποια

-καλή

, όπως ορίστηκε στο Λήμμα 3. Αν $n<m \leq i-2$ , τότε f(m)>f(m-1)+9f(n)

, οπότε

, οπότε από το Λήμμα 1 $x \nmid \displaystyle\gcd (f(m)+n, f(n)+m)$ . Αν m=i-1>n

, έστω

. Όμως $c\leq x-10^{i-1}$ , που σημαίνει ότι $0<(i-1)+n+c<2(i-1)-10^{i-1}+x<x$ , άρα $x \nmid \displaystyle\gcd (f(m)+n, f(n)+m)$ .

Απόδειξη ότι δεν υπάρχει συνάρτηση

που να είναι 1-καλή:
Έστω ότι υπάρχει τέτοια

.
Τότε αν υπάρχουν 2 περιττοί $m\neq n$ με f(n),f(m)

περιττούς, τότε 2|gcd (f(m)+n, f(n)+m)

. Άρα η

στέλνει κάποιον περιττό

σε άρτιο.
Aν υπάρχουν 2 άρτιοι $m\neq n$ με f(n),f(m)

άρτιους, τότε 2|gcd (f(m)+n, f(n)+m)

. Άρα η

στέλνει κάποιον άρτιο

σε περιττό.
Αλλά τότε $f(i)+j \equiv f(j)+i \equiv 0 (mod 2)$ . Άτοπο.

#20

GVlachos έγραψε: 'Εστω ότι όλοι οι ακέραιοι μεγαλύτεροι ή ίσοι κάποιου είναι καθαροί.
$s_1<s_2<\cdots<s_n<\cdots$ τα στοιχεία του και ο ελάχιστος δείκτης για τον οποίο .
Επίσης θα λέμε ότι ένας αριθμός έχει περιττή(άρτια) αναπαράσταση αν μπορεί να γραφεί ως άθροισμα περιττού(άρτιου) το πλήθος στοιχείων του .

Ξεκινάω με τα βήματα της απόδειξης. Η απόδειξη για κάθε βήμα ακολουθεί από κάτω:
1) Για ισχύει $y \geq 2x-k$
2) $S_{i=1}^{j-1}s_i < s_j+k log(s_j)$ .
3) Υπάρχει σταθερά ώστε κάθε να γράγεται με μοναδικό τρόπο ως άθροισμα άρτιου το πλήθος στοιχείων του .
4) Έστω και ο ελάχιστος δείκτης για τον οποίο . Τότε $S_{i=z}^{j-1}s_i < s_j$ για .
5) Υπάρχει ώστε για κάθε , $\sum_{i=1}^{j-1}s_i<2s_j$ .

Γιώργο, ευχαριστούμε για τη συμμετοχή και την όμορφη λύση

Βάζω ένα διαφορετικό τελείωμα από εδώ και πέρα: (Μπορεί να το ελέγξει κάποιος; )
Είναι άμεσο ότι αν $s,t\in S$ με t>s>K

τότε η άρτια αναπαράσταση του

περιέχει το

.
Οπότε για κάθε s_j>L

θα έχουμε ότι γράφεται στη μορφή $s_j=s_{j-1}+\ldots+s_z+Y_j$ όπου το Υ_j

είναι το υπόλοιπο, δηλαδή άθροισμα στοιχείων $s_1,\ldots, s_{z-1}$
Παίρνω το δείκτη j_0

με το μικρότερο υπόλοιπο. Τότε από την επιλογή του j_0

$\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}$ έχει περιττή αναπαράσταση διαφορετική από τον εαυτό του, άτοπο.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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