Εύρεση ελαχίστου

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ · #1

Εστω $x_{i}\in \left \{ 0,-1,1 \right \},i=1,2,...k$

Να βρεθεί η ελάχιστη τιμή του

$S=\sum _{1\leq i< j\leq k}x_{i}x_{j}$

#2

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

Δημήτρη, ευχαριστώ.

#3

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

.

Έχουμε $x_1^2 + \cdots + x_k^2 + 2S = (x_1 + \cdots + x_k)^2$ .

Έστω ότι

από τα

ισούνται με

και

ισούνται με

. (Όπου $a+b \leqslant k$ .) Τότε:

$\displaystyle 2S = (a-b)^2 - (a+b) \geqslant 0 - k = -k$

οπότε $S \geqslant -k/2$ . Επειδή όμως

ακέραιος τότε είναι $S \geqslant \lfloor -k/2 \rfloor$ . Δηλαδή:

Για k = 2n

έχουμε $S \geqslant -n$ . Η ισότητα λαμβάνεται αν $x_1 = \cdots = x_n = 1$ και $x_{n+1} = \cdots = x_{2n} = -1$ .
Για k = 2n+1

έχουμε $S \geqslant -n$ . Η ισότητα λαμβάνεται αν $x_1 = \cdots = x_n = 1, x_{n+1} = \cdots = x_{2n} = -1$ και $x_{2n+1} = 0$ .

#4

Demetres έγραψε: ↑
Κυρ Ιαν 14, 2018 10:44 pm
Μιχάλη, κάτι πρέπει να πήγε λάθος. Η παράσταση που ξεκινάς δεν ισούται με το .

Δημήτρη, έχεις δίκιο. Την πάτησα.