Кабинет Информатики

Онлайн-олимпиада «Универсальные компетенции в программировании и информатике» от Московского педагогического государственного университета, Учи.ру и Лондонского университета

 Варианты решения заданий отборочного тура онлайн-олимпиады «Универсальные компетенции в программировании и информатике» (10 и 11 класс). Олимпиада проводится образовательной платформой UCHi.RU и Московским педагогическим государственным университетом (МПГУ).

Задания отборочного тура олимпиады
«Универсальные компетенции в программировании и информатике»

«Незаменимые игроки»

 В футбольной команде 30 игроков, среди них 18 нападающих, 11 полузащитников, 17 защитников и вратари. Известно, что трое могут быть нападающими и защитниками, 10 - защитниками и полузащитниками, 6 - нападающими и полузащитниками, а один и нападающим, и защитником, и полузащитником. Вратари незаменимы. Сколько в команде вратарей?

Решение:
 Для решения задачи используем метод с диаграммами Эйлера-Венна.

 Один игрок может быть и нападающим, и защитником, и полузащитником, следовательно, два игрока (2 = 3 - 1) могут быть ТОЛЬКО нападающими и защитниками и не могут быть полузащитниками. Девять игроков (9= 10 - 1) могут быть защитниками и полузащитниками, но НЕ МОГУТ быть нападающими. Пять игроков (5 = 6 - 1) могут быть нападающими и полузащитниками, но не могут быть защитниками и т.д.

 В итоге мы получаем, что: 1 + 2 + 5 + 10 + 5 + (-4) = 29 и игроков и 30 - 28 = 2 вратаря.

Ответ: 2

«Предположение о победе»

 Перед олимпиадой по информатике ученики высказали свои предположения. 11 «А»: Игорь победит, а Фёдор займёт второе место; 11 «Б»: Фёдор будет третьим, а Саша первым; 11 «В»: Игорь станет последним, а Андрей - первым. Оказалось, что каждый класс был прав только в одном из своих прогнозов. Соедини имена победителей олимпиады и места, которые они заняли.

Решение:
 Запишем высказывания трёх классов в табличную форму (заголовок строки обозначает место на олимпиаде).

 Считая, что два человека не могут оказаться на одном месте, начнем «раскручивать» таблицу с того столбца, где больше всего информации (в данном случае - с первого).
Предположим, что Игорь действительно занял первое место, как и сказал 11 «А»; в этом случае 11 «В» ошибся, поставив на первое место Андрея. Учитывая, что каждый класс один раз угадал, а второй ошибся, получается, что 11 «В» угадал, что Игорь будет на четвертом месте. Но мы предположили, что Игорь - на первом месте (а не на четвертом), следовательно, получили противоречие; это значит, что Игорь все-таки не на первом месте. Таким образом, в первом прогнозе 11 «А» ошибся, это значит, что во втором он угадал, и Фёдор действительно занял второе место (смотрим таблицу первого этапа рассуждений).

Первый этап рассуждений:

 Так как Фёдор - второй, он не может быть на третьем месте, поэтому из прогноза 11 «Б» следует, что Саша - первый (смотрим таблицу второго этапа рассуждений).

Второй этап рассуждений:

Если Саша на первом месте, там не может быть Андрей, поэтому из ответов 11 «В» (среди которых должен быть один верный и один неверный) сразу находим, что Игорь занял четвертое место.
Осталось только определиться с Андреем - ему досталось единственное «свободное» третье место.

Окончательный список победителей будет выглядеть так: Саша - 1 место, Фёдор - 2 место, Андрей - 3 место, Игорь - 4 место.

«Иностранные языки»

 В компании 67 сотрудников. Из них 47 знают французский язык, 35 - немецкий язык, а 23 человека знают оба языка. Сколько человек в компании не знают ни французского, ни немецкого? Впиши ответ.

Решение:
 Решаем задачу с помощью диаграмм Эйлера-Венна.

24 + 23 + 12 = 59 сотрудников знают хотя бы один язык;
67 - 59 = 8 человек не знают ни французского, ни немецкого языков.

Ответ: 8

«Оценки»

 Учитель сказал трём ученикам: «Вы все получили разные оценки - 3, 4, 5. У Иванова не 4, у Петрова не 5, а вот у Кузнецова, кажется 4». Оказалось, что учитель верно назвал оценку только одного из ребят. Соедини имена учеников и оценки, которые они получили.

Решение:

 Внесём рассуждения по трём ученикам в табличную форму.

Рассуждения для решения задачи:

Ответ: Кузнецов - 5, Иванов - 4, Петров - 3.

«Спорт»
В школе 1400 учеников. Из них 1250 умеют кататься на горных лыжах, 952 - на сноуборде. 60 учащихся не умеют кататься ни на горных лыжах, ни на сноуборде. Сколько учащихся умеют кататься и на сноуборде, и на горных лыжах? Впиши ответ.

Решение:
Решаем задачу с помощью диаграмм Эйлера-Венна.

1400 - 60 = 1340 учеников умеют кататься на чем-либо (горные лыжи и (или) сноуборд);
(1250 - x) + (952 - x) + x = 1340
x = 862 ученика умеют кататься и на сноуборде, и на горных лыжах

Ответ: 862

«Жизнь студентов»

В одном общежитии в разных комнатах на одном этаже живут четыре студентки: Оля, Даша, Лина и Наташа. Все они с разных факультетов: психологии, лингвистики, биологии, политологии. Известно, что:
1) студентка факультета психологии живёт левее студентки лингвистки;
2) студентка факультета биологии живёт правее студентки факультета политологии;
3) студентка факультета политологии живёт рядом со студенткой факультета лингвистики;
4) студентка факультета психологии живёт рядом со студенткой факультета лингвистики;
5) Лина живёт правее студентки факультета политологии;
6) Наташа не учится на факультете психологии;
7) Даша живёт рядом со студенткой факультета лингвистики;
8) Лина живёт левее Даши.
Кто где живёт и кто где учится? Перемещай имена и названия факультетов между комнатами.

Решение:

Введём обозначения: О - Оля, Д - Даша, Л - Лина, Н - Наташа

Пс - факультет психологии;
Лг - факультет лингвистики;
Би - факультет биологии;
Пл - факультет политологии.

Начнём с первого условия и выпишем варианты, которые удовлетворяют ему (это первая строка). Далее будем накладывать следующее условие на выбранные варианты. И так будем делать до тех пор, пока не рассмотрим се условия. Ниже на рисунке описан ход решения.

«Комбинация цифр»
 Сейф запирается на замок, состоящий из 5 дисков. На каждом из дисков изображены цифры 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Замок открывается, если на дисках набрана одна определённая комбинация цифр. Хватит ли 10 дней, чтобы открыть сейф, если каждый день на это есть 13 часов, а на набор одной комбинации цифр уходит 5 с? Впишите ответ (да/нет).

Решение:

Возможных комбинаций в данном случае 100.000. Т.е. разница между 99999 и 00000.

Для перебора всех комбинаций потребуется: 100000 * 5 с = 500 000 секунд = 8333 минут = 139 часов = 10,7 дней.

Ответ: Нет

«Монеты в коллекции»
 У девочки есть 15 юбилейных монет: 6 монет с изображением Москвы, 4 монеты с изображением Сочи, а остальные с изображением Самары. Сколькими способами девочка может разложить коллекцию из всех своих монет? Впиши ответ.

Решение:
 Это задача на перестановки с повторениями.

 Перестановками с повторениями называются перестановки из n элементов, в каждую из которых входит n₁ элементов a, n₂ элементов b, ..., n_k элементов I, где n=n₁ + n₂ + ... + n_k. Число перестановок с повторениями вычисляется по формуле: P (n₁, n₂, ... , n_k) = n! / n₁!n₂!...n_k!

 У нас есть монеты трёх различных видов: с Москвой n₁=6, с Сочи n₂=4 и с Самарой n₃=5. Всего монет n=15.

 Следовательно, по указанной выше формуле имеем:

P(6,4,5) = 15! / 6!4!5! = (15*14*13*12*11*10*9*8*7) / (4*3*2*5*4*3*2) = 630630 (способов)

Ответ: 630630

«Количество имён»

 У англичан принято давать детям несколько имён. Сколько комбинаций имён существует для каждого ребёнка, если общее число имён - 300, а ребёнку дают не более трёх имён? Впиши ответ.

Решение:

 Ключевая фраза в задаче «не более трёх имён». Это значит, что ребёнку могут дать и одно имя, и два имени.

1 имя - 300 вариантов (первое имя можно выбрать из 300)

2 имени - 300 * 299 = 89700 вариантов (первое имя можно выбирать из 300, второе - из 299)

3 имени - 300 * 299 * 298 = 26730600 вариантов (первое имя из 300, второе - из 299, третье - из 298)

Итого получим: 300 + 89700 + 26 730 600 = 26 820 600 комбинаций.

Ответ: 26820600

«Больше ста»

 Сколько чисел больше 100 можно записать с помощью цифр 1,2,3,4, если в каждом числе каждая цифра используется не более одного раза? Впиши ответ.

Решение:

 Правило произведения гласит, что если объект A может быть выбран n способами и после каждого из таких выборов объект B - m способами, то выбор «A и B» в указанном порядке может осуществлен n*m способами.

 Сначала выясним сколько различных четырёхзначных чисел можно составить из цифр 1,2,3,4.

 На первое место в четырёхзначном числе можно выбрать любую цифру из четырёх. После каждого такого выбора на второе место можно поставить любую цифру из оставшихся трёх, не третье - из оставшихся двух, на четвёртое - одну оставшуюся цифру.
 По правилу произведений получим: 4 * 3 * 2 * 1 = 24 четырехзначных числа можно составить.

 Таким образом, мы получили, что между 1234 и 4321 можно составить 24 комбинации.

 Теперь выясним сколько различных трёхзначных чисел можно составить из цифр 1, 2, 3, 4.
 По правилу произведений получим: 4 * 3 * 2 = 24 трёхзначных числа можно составить. Т.е. столько же, как и в случае с четырёхзначными числами.

 Так как на требуется записать числа больше 100, т.е. трёхзначные и более, то получаем: 24 + 24 = 48 чисел.

Ответ: 48

Решение для 8-9 класса =>>>