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)$

Наибольшим целым $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

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

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

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

С.Токарев

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

Всякая первообразная $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$ .

Спойлер

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

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

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

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

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

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

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

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

[свернуть]

Замечание

Условие непрерывности функции $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$ .

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

Свойство 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$ .

Спойлер

$\square$

$\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}$ ,

т.е.

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

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

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

[свернуть]

Замечание

Если $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 |$ .

Литература

Лысенко З.М.. Конспект лекций по математическому анализу
Ильин В.А., Позняк Э.Г. Основы математического анализа. М.:Наука, 1982, стр.333
Фихтенгольц Г.М. Курс дифференциального и интегрального исчисления. М.:Наука, 1969, стр.112-113

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

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

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

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

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

Спойлер

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

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

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

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

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

[свернуть]

Пример

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

Спойлер

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

[свернуть]

Литература

Лысенко З.М.. Конспект лекций по математическому анализу

Ильин В.А., Позняк Э.Г. Основы математического анализа. М.:Наука, 1982, стр.333

Фихтенгольц Г.М. Курс дифференциального и интегрального исчисления. М.:Наука, 1969, стр.111-112

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

Определенный интеграл

Свойства определенного интеграла связанные с неравенствами

Автор Денис СтехунОпубликовано 19/05/201306/06/2014Рубрики Математический анализМетки интеграл, монотонность, определённый интеграл, свойство монотонностиДобавить комментарий к записи Свойство монотонности интеграла

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

Свойство 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$ .

Спойлер

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

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

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

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

тогда

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

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

[свернуть]

Пример

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

Спойлер

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

[свернуть]

Литература

Лысенко З.М.. Конспект лекций по математическому анализу

Ильин В.А., Позняк Э.Г. Основы математического анализа. М.:Наука, 1982, стр.333

Фихтенгольц Г.М. Курс дифференциального и интегрального исчисления. М.:Наука, 1969, стр.110-113

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

Определенный интеграл

Свойства определенного интеграла связанные с неравенствами

Автор Денис СтехунОпубликовано 19/05/201306/06/2014Рубрики Математический анализМетки интеграл, определённый интеграл, положительная функция1 комментарий к записи Интеграл от положительной функции

Пагинация записей

Страница 1 Страница 2 Следующая страница