Школьник сказал своему приятелю Вите Иванову: — У нас в классе 25 человек. И представь, каждый из них дружит ровно с 5 одноклассниками...
— Не может этого быть, — сразу ответил Витя Иванов, победитель математической олимпиады. Почему он так решил?

Дополни решение задачи.

Представим себе, что между каждыми двумя друзьями протянута ниточка. Тогда каждый из 25 учеников будет держать в руке
концов ниточек, и значит, что всего у протянутых ниточек будет
концов (конец, конца). Но общее число не может быть нечётным, так как у каждой ниточки 2 конца.

👇

Ответ:

TheFlyHelp

17.02.2020

НЕ МОЖЕТ БЫТЬ ТАКОГО

Объяснение:

Представим себе, что между каждыми двумя друзьями протянута ниточка. Тогда каждый из 25 учеников будет держать в руке 15 концов ниточек, и значит, всего у протянутых ниточек будет 15*25 концов. Но общее число не может быть нечётным, так как у каждой ниточки 2 конца.

4,7(40 оценок)

Открыть все ответы

Ответ:

natalijamatijch

17.02.2020

Каждая из компонент связности должна быть кликой (иначе говоря, каждые две вершины в одной компоненте связности должны быть связаны ребром). Если в i-ой компоненте связности n_i

вершин, то общее число рёбер будет суммой по всем компонентам связности:

$\displaystyle \sum_{i=1}^K\frac{n_i(n_i-1)}2=\frac12\sum_{i=1}^K n_i^2-\frac12\sum_{i=1}^Kn_i=\frac12\sum_{i=1}^K n_i^2-\frac N2$

Требуется найти максимум этого выражения (т.е. на самом деле - максимум суммы квадратов) при условии, что сумма всех ni равна N и ni - натуральные числа.

Если K = 1, то всё очевидно - ответ N(N - 1)/2. Пусть K > 1.

Предположим, n1 <= n2 <= ... <= nK - набор чисел, для которых достигается максимум, и n1 > 1. Уменьшим число вершин в первой компоненте связности до 1, а оставшиеся вершины "перекинем" в K-ую компоненту связности. Вычислим, как изменится сумма квадратов:
$\Delta(\sum n_i^2)=(1^2+(n_K+n_1-1)^2)-(n_1^2+n_K^2)=2(n_1-1)(n_K-1)$
Поскольку по предположению n1 > 1 (тогда и nK > 1), то сумма квадратов увеличится, что противоречит предположению о том, что на выбранном изначально наборе достигается максимум. Значит, максимум достигается, если наименьшая по размеру компонента связности - изолированная вершина. Выкинем эту компоненту связности, останутся K - 1 компонента связности и N - 1 вершина. Будем продолжать так делать, пока не останется одна вершина, тогда получится, что во всех компонентах связности кроме последней должно быть по одной вершине.

Итак, должно выполняться
$n_1=n_2=\cdots=n_{K-1}=1;\qquad n_K=N-K+1$

Подставив в исходную формулу, получаем
$\displaystyle\frac{(N-K)(N-K+1)}{2}$

Это и есть ответ.

4,7(55 оценок)

Ответ:

алина3903

17.02.2020

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

2) На первом месте несомненно располагается китайский язык. Второе место принадлежит испанскому языку, который является официальным в 20 странах. Очень интересный иностранный язык расположился на третьем мест — хинди, на нем говорит население Индии.

3) Формальный язык однозначен и не допускает толкований. При выполнении его инструкций результат также однозначен, что имеет огромное значение при производстве вычислений и построении числовых моделей, что позволяет судить о правильности их построения.

4,7(17 оценок)

Это интересно:

Образование

05.08.2020

Решить систему уравнений x2 + xy +y2 = 13...

Образование

16.03.2023

Решить систему уравнений x2 + y2 + xy = 3...

Образование

06.01.2021

Клюква стоит 250 рублей за кг, а малина 200....

Кулинария-и-гостеприимство