689
правок
Изменения
м
Так как <tex> \sum\limits_{\substack{i, j = 1\\ i \ne j}}^{k} n_i n_j \ge \sum\limits_{\substack{i, j = 1\\ i \ne j}}^{k} 1 \cdot n_j = \sum\limits_{j = 1}^{k} (k - 1) n_j = (k - 1) (n - 1) \ge \frac{nk}{4}</tex>
→Время работы
Чтобы получить максимальную нижнюю оценку на <tex> a </tex>, оценим снизу <tex> \sum\limits_{i, j = 1}^{k} n_i n_j </tex>:
Значит, при <tex> a \ge \frac{c}{2} \frac{n}{\frac{nk}{4}} = \frac{2c}{k} </tex> требуемое неравенство будет выполняться.
