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

Условие

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

Ответ: 25.

Решение

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

[latex]x\leq28\frac{k}{k+1}+1[/latex] [latex](1)[/latex]

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

[latex]\frac{k+1}{2}\leq30-x[/latex] [latex](2)[/latex]

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

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

[latex]k\leq59-2x[/latex] [latex](3)[/latex]

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

[latex]x^{2}-59x+856\geq0[/latex] [latex](4)[/latex]

К задаче M1656

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

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

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. в верхней строке.

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

С.Токарев

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

Всякая первообразная $latex F(x)$ для $latex f(x)$, где $latex f$ непрерывна на $latex [a,b] $, имеет вид
$latex 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непрерывности функции $latex f$, тогда

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

Спойлер

$latex \square$ Пусть $latex x _{0} \in (a,b) :\lim\limits_{x\rightarrow x_{0}}f(x)=f(x_{0})> 0 $. Тогда

$latex \exists \; U_{\delta }(x_{0}):f(x)> \frac{f(x_{0})}{2}$,

следовательно

$latex \int\limits_{x_{0}-\delta}^{x_{0}+\delta}\frac{f(x_{0})}{2} dx = \frac{f(x_{0})}{2}\int\limits_{x_{0}-\delta}^{x_{0}+\delta}dx =\frac{f(x_{0})}{2}\cdot 2\delta> 0$.

Так как имеют место неравенства

$latex \int\limits_{a}^{x_{0}-\delta} f(x) dx \geqslant 0, \int\limits_{x_{0}-\delta}^{x_{0}+\delta}f(x)dx > 0 , \int\limits_{x_{0}+\delta}^{b}f(x)dx \geqslant 0$

и

$latex \int\limits_{a}^{b}f(x)dx = \int\limits_{a}^{x_{0}-\delta}f(x)dx +\int\limits_{x_{0}-\delta}^{x_{0}+\delta}f(x)dx+\int\limits_{x_{0}+\delta}^{b}f(x)dx$,

то получим $latex \int\limits_{a}^{b}f(x)dx >0$.$latex \blacksquare$

[свернуть]
Замечание

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

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

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

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

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

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

Спойлер

$latex \square$

$latex \left | \sum\limits_{i=1}^{n}f(\xi_{i})\Delta x_{i} \right | \leqslant \sum\limits_{i=1}^{n}\left | f(\xi_{i}) \right |\Delta x_{i}$,

т.е.

$latex \left|\delta_{T}(f,\xi)\right|\leqslant\delta_{T} (\left|f\right|,\xi)$.

Переходя к пределу при ранге разбиения стремящемуся к нулю, получим

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

[свернуть]
Замечание

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

$latex \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

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

Спойлер

$latex \square$Пусть $latex \phi(x) \equiv f(x)-g(x)$, тогда $latex \phi \in R[a,b]$ и $latex \phi \geqslant 0$. По свойству интеграла от положительной функции

$latex \int\limits_{a}^{b}(f(x)-g(x))dx \geqslant 0 $,

тогда получим что

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

Что и требовалось доказать.$latex \blacksquare$

[свернуть]
Пример

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

Спойлер

Заметим, что $latex \ln{x}\geqslant \ln{3}>\ln {e=1},\forall\;x\in[3,4]$ поэтому $latex \ln^{2}{x}>\ln{x},\;\forall\;x\in[3,4]$. Тогда, по свойству монотонности интеграла  $latex \int\limits_{3}^{4}\ln{x}dx < \int\limits_{3}^{4}\ln^{2}{x}dx$.

[свернуть]
Литература
Смотрите так же

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

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

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

Спойлер

$latex \square$Рассмотрим интегральную сумму Дарбу для данного интеграла

$latex \delta _{T}(\xi ,f)=\sum\limits_{i=1}^{n}f(\xi _{i})\Delta x_{i}$.

Поскольку $latex f(\xi _{i})\geqslant 0$ и $latex \delta x_{i}\geqslant 0$, то и

$latex \delta _{T}(\xi ,f)=\sum\limits_{i=1}^{n}f(\xi _{i})\Delta x_{i} \geqslant 0$,

тогда

$latex \int\limits_{a}^{b}f(x)dx=\lim\limits_{\lambda\rightarrow 0}\delta _{T}(\xi ,f) \geqslant 0$.

Что и требовалось доказать.$latex \blacksquare$

[свернуть]
Пример

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

Спойлер

Рассмотрим подынтегральную функцию $latex f(x)=x^{2}+3$. Поскольку $latex f(x)>0 , \; \forall \; x \in [1,2]$, то по свойству интеграла от положительной функции  $latex \int\limits_{1}^{2}(x^{2}+3)dx > 0$.

[свернуть]
Литература
Смотрите так же