Ελάχιστος ακέραιος

#1

Έστω

θετικός ακέραιος και f(n)

ο ελάχιστος ακέραιος τέτοιος ώστε σε οποιουσδήποτε f(n)

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

Βρείτε το

#2

Επαναφορά!

#3

Την θεωρώ δύσκολη άσκηση γι' αυτό και θα την μεταφέρω από το «Επίπεδο Αρχιμήδη (Seniors)» στο «Προχωρημένο Επίπεδο (Seniors)»

Μπήκε πέρσι στον διαγωνισμό επιλογής του Ιράν και είναι η άσκηση 69 εδώ.

Βάζω την νύξη που είχα δώσει:

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

dement · #4

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

τους επιλεγέντες αριθμούς.

Έστω n = 2k+1

. Για πλήθος όρων 4k+1

μπορούμε να επιλέξουμε $a_m \equiv 1 \mod 2k+1$ για κάθε

(και το ζητούμενο είναι αδύνατο). Αντίθετα, για πλήθος 4k+2

, μεταξύ των 4k+3

ισοτιμιών των $\displaystyle \sum_{m=1}^t a_m \ (0 \leqslant t \leqslant 4k+2)$ θα υπάρχουν τρεις ίδιες (έστω p < q < r

), οπότε ένα από τα $\displaystyle \sum_{m=p+1}^q a_m, \sum_{m=q+1}^r a_m, \sum_{m=p+1}^r a_m$ , που διαιρούνται με το 2k+1

, θα έχει άρτιο πλήθος όρων. Έτσι, f(2k+1) = 4k + 2

.

Παρατηρούμε ότι χωρίς τον περιορισμό του αρτίου πλήθους θα ίσχυε f(n) = n

για κάθε

(περιττό ή άρτιο). Πράγματι, για πλήθος n-1

μπορούμε να επιλέξουμε όλους τους αριθμούς ισότιμους με $1 \mod n$ (και το ζητούμενο είναι αδύνατο). Αντίθετα, για πλήθος

, μεταξύ των n+1

ισοτιμιών των $\displaystyle \sum_{k=1}^m a_k \ (0 \leqslant m \leqslant n)$ θα υπάρχουν δύο ίδιες (έστω p < q

), οπότε $\displaystyle n \mid \sum_{k=p+1}^q a_k$ .

Για n = 2k

,

αφού μπορούμε να επιλέξουμε $a_1 \equiv 2 \mod 2k$ και $a_m \equiv 1 \mod 2k$ για m > 1

(και το ζητούμενο είναι αδύνατο). Για πλήθος 2k+1

, διαχωρίζουμε τα άρτια από τα περιττά a_m

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

ζεύγη όρων, ξένα μεταξύ τους, όπου το κάθε ζεύγος έχει άρτιο άθροισμα. Έτσι, θεωρώντας τις ισοτιμίες $\mod k$ των ημιαθροισμάτων σε κάθε ζεύγος, το πρόβλημα ανάγεται στην περίπτωση n = k

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

, γνωρίζουμε ότι είναι επιλύσιμη. Άρα f(2k) = 2k+1

.

Ελάχιστος ακέραιος

Ελάχιστος ακέραιος

Re: Ελάχιστος ακέραιος

Re: Ελάχιστος ακέραιος

Re: Ελάχιστος ακέραιος

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