РЕШУ ОЛИМП: задания, ответы, решения

Задания

Версия для печати и копирования в MS Word

Тип 0 № 2482 Добавить в вариант

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

Спрятать решение

Решение.

Пусть для простоты рейтинги теннисистов равны $1, 2, \ldots, n.$ Одна расстановка очевидна  — по убыванию рейтинга. В других расстановках убывание нарушается. Это может происходить только из-за присутствия пар соседей $левая круглая скобка 1, n правая круглая скобка$ и $левая круглая скобка 2, n минус 1 правая круглая скобка$ (какой-то одной или обеих). Рассмотрим три случая.

1)  Bстречается только пара $левая круглая скобка 1, n правая круглая скобка .$ До и после этой пары может быть любое количество теннисистов, но их порядок фиксирован. Припишем спортсмену индекс 0, если он стоит слева от пары, и 1, если справа. Для каждого из оставшихся $n минус 2$ теннисистов допустимы оба индекса, поэтому всего будет $2 в степени левая круглая скобка n минус 2 правая круглая скобка$ расстановок.

2)  Bстречается только пара $левая круглая скобка 2, n минус 1 правая круглая скобка .$ Поскольку пары $левая круглая скобка n минус 1, n правая круглая скобка$ и (1, 2) недопустимы, теннисист с рейтингом n должен стоять первым в ряду, а теннисист с рейтингом 1  — последним. Остальные $n минус 4$ спортсмена могут стоять как до пары $левая круглая скобка 2, n минус 1 правая круглая скобка ,$ так и после нее, но в фиксированном порядке. Таких расстановок всего $2 в степени левая круглая скобка n минус 4 правая круглая скобка .$

3)  Встречаются пары $левая круглая скобка 1, n правая круглая скобка$ и $левая круглая скобка 2, n минус 1 правая круглая скобка .$ Любой из остальных $n минус 4$ теннисистов может располагаться до первой пары, между парами и после второй пары. Таких расстановок всего $3 в степени левая круглая скобка n минус 4 правая круглая скобка .$ Поскольку пары $левая круглая скобка 1, n правая круглая скобка$ и $левая круглая скобка 2, n минус 1 правая круглая скобка$ могут идти в любом порядке, мы получаем $2 умножить на 3 в степени левая круглая скобка n минус 4 правая круглая скобка$ вариантов.

Таким образом, всего возможно

$1 плюс 2 в степени левая круглая скобка n минус 2 правая круглая скобка плюс 2 в степени левая круглая скобка n минус 4 правая круглая скобка плюс 2 умножить на 3 в степени левая круглая скобка n минус 4 правая круглая скобка$

расстановок.

Ответ: $1 плюс 2 в степени левая круглая скобка n минус 2 правая круглая скобка плюс 2 в степени левая круглая скобка n минус 4 правая круглая скобка плюс 2 умножить на 3 в степени левая круглая скобка n минус 4 правая круглая скобка .$

Спрятать критерии

Критерии проверки:

Общая схема:

0 баллов  — выставляется, если участник к решению задачи не приступал или начатый ход решения полностью неверен;

1 балл  — выставляется, если участник приступил к решению задачи, указал верное направление решения задачи и получил правильные промежуточные результаты, но при этом не продвинулся настолько, чтобы можно было судить о том, каким образом он собирался получить окончательный ответ (то есть весь ход решения не представлен);

2 балла  — выставляется, если выбранный участником ход решения задачи является в принципе правильным, но при этом участник не смог его реализовать в силу серьёзных ошибок;

3 балла  — выставляется, если решение является в целом правильным, но содержит ошибки, повлиявшие на ответ;

4 балла  — выставляется, если участник решил задачу в целом правильно и получил верный ответ; при этом в решении допускаются незначительные неточности.

Факторы, влияющие на оценку.

1.  Одна из основных целей Олимпиады  — выявление у обучающихся творческих способностей. Поэтому в случае представления участником интересного оригинального подхода к решению задачи, оценка за решение может быть увеличена на 1 балл.

2.  Правильный ответ к задаче, приведенный без достаточных обоснований, либо при наличии ошибок в решении, либо при отсутствии решения, не ведёт к увеличению оценки, которая выставляется участнику за данную задачу.

3.  Если участник не довел задачу до ответа, то итоговая оценка за данную задачу не может превышать 1 балл.

4.  Если задача решена перебором возможных вариантов, и при этом перебор неполный, то за задачу выставляется до 1 балла. Если участник подобрал частное решение без обоснования и проверил его правильность, то в этом случае за задачу выставляется до 0,5 баллов.

5.  Если задача решена при дополнительном предположении, которое отсутствует в условии, то за задачу выставляется

а)  до 1 балла, если это предположение можно доказать;

б)  до 0,5 баллов, если оно не обязано выполняться, но не противоречит условию задачи;

в)  0 баллов, если оно противоречит условию.

6.  Если в работе приведены два решения или ответа к одной задаче, противоречащие друг другу, то за задачу ставится 0 баллов.

Олимпиада СПБГУ, 11, 10 класс, 2 тур (заключительный), 2019 год

Классификатор: Комбинаторика, вероятность, статистика. Размещения, перестановки и сочетания, Разное. Турниры

Спрятать решение · Спрятать критерии · Помощь