Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела спбгу
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#76025

В театре k  рядов кресел. 770  зрителей пришли в театр и расселись по местам (заняв, возможно, не все кресла). После антракта все зрители забыли, на каких местах они располагались, и сели по-другому. При каком наибольшем k  заведомо найдется 4  зрителя, которые и до, и после антракта сидели на одном ряду?

Источники: СПбГУ-16, 11.4

Показать ответ и решение

Если зрители расселись на 16  рядов, то на каком-то ряду оказалось не менее 49  зрителей (в противном случае на каждом ряду не более 48  зрителей, а всего их тогда не более 16⋅48= 768 <770  ). Так как 49-
16 >3,  нельзя рассадить зрителей этого ряда после антракта так, чтобы в каждом ряду их оказалось не более трех. Таким образом, k =16  нас устраивает.

Покажем теперь, что при наличии 17  рядов зрителей можно рассадить так, чтобы нужных четырех зрителей не нашлось. Назовем   n  -й колонкой места в зале с номером n,  циклически упорядоченные по рядам:

1,2,...,17,1,2,...,17,... (∗)

Пусть циклический сдвиг колонки на m  рядов — перестановка колонки, при которой новый номер ряда каждого зрителя получается из старого сдвигом на m  позиций вправо в последовательности (∗).  Заполним зрителями колонки с номерами от 1  по 45,  а также первые 5  мест 46  -й колонки. Таким образом, в зале окажется 17⋅45+5 =770  человек. После антракта мы рассадим зрителей следующим образом. Зрители колонок 1,2,3  садятся на свои места; в колонках 4,5,6  зрители циклически сдвигаются на один ряд, в колонках 7,8,9  — на два ряда, и так далее. В результате мы получим ситуацию, когда нет четырех зрителей, сидевших на одном ряду и до, и после антракта.

Ответ:

 16

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное обучение
в Школково

Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!