Тема Всесиб (Всесибирская открытая олимпиада школьников)

Логика на Всесибе

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела всесиб (всесибирская открытая олимпиада школьников)

Решаем задачи

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

Задача 1#66866

На некотором острове живёт $100$ человек, каждый из которых является либо рыцарем, который всегда говорит правду, либо лжецом, который всегда лжёт.

Однажды все жители этого острова выстроились в ряд, и первый из них сказал:

“Количество рыцарей на этом острове является делителем числа

Затем второй сказал:

“Количество рыцарей на этом острове является делителем числа

и так далее до сотого, который сказал:

“Количество рыцарей на этом острове является делителем числа

Определите, сколько рыцарей может проживать на этом острове. Найдите все ответы и докажите, что других нет.

Источники: Всесиб-2022, 7.4 (см. sesc.nsu.ru)

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

Если рыцарей нет, то все говорящие врут, так как $0$ не является делителем какого-либо натурального числа.

Если рыцари есть, то пусть первый рыцарь имеет номер $x.$ Тогда число рыцарей является делителем числа $x,$ но не будет являться делителем чисел $1,2...,x− 1,$ поскольку до него все лгали. Легко видеть, что тогда число рыцарей равно $x.$ Тогда ему кратны только числа $x,2x,3x,...,kx.$ Здесь $kx≤ 100,(k+1)x> 100.$ Ровно на этих позициях и только на них и должны стоять рыцари, откуда всего их будет $k= x.$ Имеем $2 x ≤ 100,x(x+ 1)> 100.$ Под это условие подходит только $x= 10.$ В качестве примера достаточно поставить рыцарей на позиции $10,20,...100.$

Ответ:

$0$ и $10$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

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

Задача 2#38861

В кружке занимались $50$ школьников, которые иногда ходили на занятия. Оказалось, что любые два школьника встретились на каком-либо занятии ровно один раз. Кроме того, известно, что ни на одно занятие не приходили все школьники одновременно. Докажите, что есть школьник, который был хотя бы на $8$ занятиях.

Источники: Всесиб-2020, 7.5 (см. sesc.nsu.ru)

Показать доказательство

Предположим, что это не так, то есть каждый школьник был не более, чем на $7$ занятиях. Тогда по принципу Дирихле на одном из них он встретил хотя бы $7$ школьников (оставшихся школьников $49$ ). Пусть это было занятие по математике. По условию на нём были не все школьники, поэтому также найдётся такой, который на нём отсутствовал (назовём его Вася). Вася должен встретить всех школьников (которых как минимум $8$ ) с математики на других занятиях. Но раз между собой математики уже виделись, то встречи между ними произошли на разных восьми занятиях. Вася должен быть на всех. Получаем противоречие с тем, что каждый был не более, чем на семи занятиях.

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

Задача 3#94456

Можно ли разбить все натуральные числа от $1$ до $100$ включительно на десять множеств, содержащих различное количество чисел каждое, таких что чем больше чисел содержит множество, тем меньше сумма его элементов?

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

Предположим, указанное в условии разбиение возможно. Сумма всех чисел от $1$ до $100$ равна $5050,$ следовательно, сумма чисел во множестве с максимальной суммой не меньше $5050∕10= 505,$ поэтому оно содержит не меньше $6$ чисел. По условию, каждое из девяти оставшихся множеств содержит различное, большее шести, количество чисел. Следовательно, во всех десяти множествах содержится не меньше $6+ 7+ ...+ 15= 105$ чисел — противоречие.

Ответ:

Нет

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

Задача 4#89610

На острове проживают 20 человек, часть из них рыцари, которые всегда говорят правду, а остальные — лжецы, которые всегда лгут. Каждый островитянин точно знает, кто из остальных рыцарь, а кто — лжец. На вопрос приезжего, сколько рыцарей проживают на острове, первый из островитян ответил: “Ни одного”, второй: “Не более одного”, третий: “Не более двух”, четвёртый: “Не более трёх” и т. д., двадцатый заявил: “Не более девятнадцати”. Так сколько же рыцарей проживают на острове?

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

Если бы первый островитянин был рыцарем, то своим ответом он бы солгал, чего не может быть. Следовательно, первый — лжец и всего рыцарей на острове не больше $19.$ Значит, двадцатый островитянин своим ответом сказал правду, поэтому он рыцарь, в частности, на острове не меньше одного рыцаря. Тогда, если бы второй островитянин оказался рыцарем, их вместе с двадцатым было бы уже два, и он бы солгал, значит, второй — лжец и всего рыцарей не больше $18.$ Поэтому девятнадцатый сказал правду и он — рыцарь. Продвигаясь так дальше, несложно убедиться, что все островитяне с первого по десятого — лжецы, а все с $11$ -ого по $20$ -ого — рыцари.

Ответ: 10