M1656. Оценка числа доминирующих вершин в вершинно-взвешенном графе

Условие

В классе 30 учеников, и у каждого из них одинаковое число друзей среди одноклассников. Каково наибольшее возможное число учеников, которые учатся лучше большинства своих друзей? (Про любых двух учеников в классе можно сказать, кто из них учится лучше.)

Ответ: 25.

Решение

Учеников, которые учатся лучше большинства своих друзей, назовем хорошими. Пусть x — число хороших учеников, k — число друзей у каждого ученика. Лучший ученик класса является лучшим в k парах друзей, а любой другой хороший ученик — не менее, чем в [k/2]+1 \geqslant (k+1)/2 парах (здесь квадратные скобки обозначают целую часть числа). Поэтому хорошие ученики являются лучшими не менее чем в k+(x-1)(k+1)/2 парах.
Это число не может превышать числа всех друзей в классе, равного 30k/2=15k. Отсюда k+(x-1)(k+1)/2 \leqslant 15k или

x\leq28\frac{k}{k+1}+1 (1)

Заметим далее, что

\frac{k+1}{2}\leq30-x (2)

поскольку число учеников, лучше которых учится наихудший из хороших, не превышает 30.

Правая часть неравенства (1) возрастает с ростом k, а неравенство (2) равносильно условию

k\leq59-2x (3)

Из (1) и (3) следует, что x\leq28*\frac{59-2x}{60-2x}+1, или

x^{2}-59x+856\geq0 (4)

К задаче M1656

Наибольшим целым x, удовлетворяющим (4) и условию x \leq 30, является x=25. Итак, число хороших учеников не превышает 25, что можно проиллюстрировать на графике.

Покажем, что оно может равняться 25. Занумеруем учеников числами от 1 до 30 в порядке ухудшения успеваемости и расположим номера в таблице 6\times 5 так, как показано на рисунке.

1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
26 27 28 29 30

Пусть пара учеников является парой друзей, если их номера расположены одним из трех способов:

  1. в соседних строках и в разных столбцах;
  2. в одном столбце и один из номеров при этом находится в нижней строке;
  3. в верхней строке.

При этом, как нетрудно проверить все требуемые условия выполнены.

С.Токарев

Общий вид первообразной для непрерывной функции

Всякая первообразная F(x) для f(x), где f непрерывна на [a,b] , имеет вид
F(x)=\int\limits_{a}^{x}f(t)dt+C.

Общий вид первообразной для непрерывной функции является следствием из теоремы о существовании первообразной у непрерывной функции.

Литература
  • З.М. Лысенко. Конспект лекций по математическому анализу, 1 семестр.: О. 2012
  • В.А. Ильин, Э.Г. Позняк. Основы математического анализа. Часть 1. Издание четвертое.  М. Наука. — 1982, Стр. 341-342
  • Г.М. Фихтенгольц. Курс дифференциального и интегрального исчисления. Том 2. Издание седьмое.  М. Наука. — 1969, Стр. 115-117
Смотрите так же

Оценка модуля интеграла

Свойство 3 (оценка модуля интеграла)

Пусть $latex f \in R[a,b] (aнепрерывности функции f, тогда

\int\limits_{a}^{b}f(x)dx> 0.

Доказательство показать
Замечание

Условие непрерывности функции f(x) в точке x_{0}, где f(x_{0})>0 существенно. Например, пусть

f(x)=\left\{\begin{matrix}  0, &0<x\leqslant 1, \\  1,&x=0.  \end{matrix}\right.

Поскольку \int\limits_{0}^{1}f(x)dx=0, то неверно, что \int\limits_{0}^{1}f(x)dx>0.

Это можно проиллюстрировать на графикеexample_modular_integral_evaluation

Свойство 4 (оценка модуля интеграла)

Если f\in R[a,b], то  \left|\int\limits_{a}^{b}f(x)dx\right|\leqslant\int\limits_{a}^{b}\left|f(x)\right|dx.

Доказательство показать
Замечание

Если f(x) — интегрируема на отрезке с концами [a,b], то

\left | \int\limits_{a}^{b}f(x)dx \right | \leqslant \left | \int\limits_{a}^{b} \left | f(x)dx \right |\right |.

Литература
Смотрите так же

Свойство монотонности интеграла

Свойство 2 (свойство монотонности интеграла)

Если $latex f,g \in R[a,b] (a

\int\limits_{a}^{b}f(x)dx \geqslant \int\limits_{a}^{b}g(x)dx.

Доказательство показать
Пример

Не вычисляя интегралов, определить какой из них больше \int\limits_{3}^{4}\ln{x}dx или \int\limits_{3}^{4}\ln^{2}{x}dx

Решение показать
Литература
Смотрите так же

Интеграл от положительной функции

Свойство 1 (интеграл от положительной функции)

 Если f(x) \in R[a,b] и f(x)\geqslant 0\;\forall\;x\in[a,b]\;(a<b), то и
\int\limits_{a}^{b} f(x)dx \geqslant 0.

Доказательство показать
Пример

Не вычисляя интеграла, определить его знак \int\limits_{1}^{2}(x^{2}+3)dx.

Решение показать
Литература
Смотрите так же