Как решать задачу, пожалуйста?

Question

[Максим Короткевич]

На каникулах студенты искали интегралы. Известно, что:
Любые пять человек нашли вместе все интегралы (т. е. каждый интеграл нашел хотя бы один человек из любой пятерки).
Любые четыре человека вместе нашли не все интегралы (т. е. для любой четверки есть хотя бы один интеграл, который никто из них не нашел).
Вопрос: При каком минимальном количестве интегралов могла сложиться такая ситуация?

Comments

[Максим Короткевич]

А вдруг студентов меньше 5?

[Михаил Ливач]

Максим Короткевич, если студентов меньше 5, у вас невыполнимо первое условие "любые 5 человек нашли все интегралы"

[Василий Банников]

Максим Короткевич, то тогда по условию задачи есть как минимум один нерешенный интеграл в принципе.

[Alexandroppolus]

Михаил Ливач, можно меньше 5 студентов, см. третий комментарий к моему ответу

[Михаил Ливач]

Alexandroppolus, ответил вам там

Answer 1

[Wataru]

Нужно хотя бы 5 интегралов. Возьмем какую-нибудь пятерку людей. Если исключить первого, какой-то интеграл, взятый первым человеком, будет не взят по условию всеми остальными. Если исключить второго, будет не взят какой-то другой интеграл (ведь прошлый интеграл отсутствовал в четверке 2,3,4,5). Аналогично, можно взять еще 3 недостающих интеграла, исключая оставшихся трех людей. Итак, мы насчитали 5 каких-то уникальных интегралов, а значит их хотя бы 5.

Также можно составить пример с 5-ю интегралами: {{1},{2},{3},{4},{5}} - 5 студентов, 5 интегралов, каждый взял совой интеграл.

Вот и получается, что 5 - минимальное количество.

Comments

[Daemon23RUS]

Не выйдет так, а если 50 человек, ограничения то по количеству нет.
P.S. я был невнимателен к условию, надо же найти минимум, Ваш вариант верен для 5ти студентов.

[SunTechnik]

Daemon23RUS,
Так спрашивается, при каком минимальном количестве интегралов МОГЛА сложится такая ситуация.
То-есть универсального ответа не требуется.
И для количества интегралов меньше 5 - нет решения.

[Daemon23RUS]

SunTechnik, Все верно, это я по диагонали условие читал ...

[Михаил Ливач]

UPD: извините, невнимательно прочитал. Вопрос в задаче про количество интегралов, а не студентов. Максимум тут, очевидно, неограничен.

[Максим Короткевич]

Студентов может быть сколько угодно.

[Максим Короткевич]

Думаю, это и есть решение, позже отпишу, заранее спасибо!

[Максим Короткевич]

А если мы второго исключим, а он нашел тот же интеграл, что и первый?

[Wataru]

Максим Короткевич, Не мог второй найти тот же интеграл. Потому что этот тот интеграл, которого не хватало, когда мы первого исключили. Это тот интеграл, который взял первый и никто другой.

Вот формально: пусть T1..T5 - множества интегралов, которые взяли 1-5 чуваки. Дано T1 U T2.. U T5 = I - множество всех интегралов.

Мы взяли i1 = Any(T1 / (T2 U T3 U T4 U T5)) - любой из интегралов, который есть в первом, но его нет у всех остальных. i2 = Any(T2 / (T1 U T3 U T4 U T5)) - любой из интегралов, который есть во втором, но его нет у всех остальных. и так далее.

i1 есть в T1, но его нет в T2. i2 есть в T2, но его нет в T1. Они не могут совпадать по определению.

[Alexandroppolus]

Wataru, спасибо, что зачли мой вариант ) Как по-вашему, расклад с тремя студентами и нулем интегралов соответствует всем условиям? У меня в комментах была дискуссия на эту тему.

[Wataru]

Alexandroppolus, Технически, вы правы. Но я думаю, что этот ответ бы никак не зачли, ибо в условии подразумевается хотя бы 5 студентов. Просто составители не подумали про это.

[Alexandroppolus]

Wataru,

Просто составители не подумали про это

да, вполне возможно

Answer 2

[Alexandroppolus]

А сколько всего студентов?
Если их N человек, то надо минимум C(N, 4) = N! / (4! * (N-4)!) интрегалов.

У нас имеется C(N, 4) различных четверок студентов. Для каждой четверки определим свой уникальный интеграл, в который они не смогли. Его решили все остальные.
Таким образом, любые 4 студента не справятся ровно с одним интегралом, и любой дополнительный пятый возьмет его (1 или 2 студента обязательно входят как минимум в 1 четверку и тоже не возьмут по крайней мере 1 интеграл).

Можно ли меньше?
Тогда либо найдется четверка, для которой нет "плохого" интеграла, то есть которая может взять их все, либо (по принципу Дирихле) найдутся 2 разные четверки, у которых общий "плохой" интеграл, но тогда из них можно собрать 5 студентов, которые с этим интегралом не справятся. Т.е. как ни крути, условия не выполняются.

Comments

[Максим Короткевич]

Может быть и меньше пяти. Найти ответ в зависимости от количества студентов.

[Alexandroppolus]

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

[Alexandroppolus]

Чуть поясню к своему комментарию про N<5. Требуется, чтобы "любая пятерка студентов решила всё", и "любая четверка решила не всё". Это можно переосмыслить соответственно так: "не найдется такой пятерки, которая решила не все", и "не найдется такой четверки, которая решила всё". Таким условиям, очевидно, соответствует 1 интеграл для N==4 и 0 интегралов для N < 4

[Михаил Ливач]

Alexandroppolus, я с вами не согласен. Выражение "любая пятерка студентов решила всё" однозначно постулирует, что "пятёрка студентов существует". Таким образом, студентов не может быть меньше пяти.

[Alexandroppolus]

Михаил Ливач, "любая пятерка" - то есть "любая пятерка из множества пятерок", пусть даже и пустого. Иными словами, на пустом множестве квантор всеобщности истинен.

https://en.wikipedia.org/wiki/Vacuous_truth

[SunTechnik]

Alexandroppolus, Но требуется что бы для любой пятерки все интегралы были решены, а для любой 4-ки -не решены.

Если 5-ка пустое множеств ( студентов меньше 5) и все интегралы решены, то они будут решены и для 4-ки студентов, что пртиворечит условию.

Вопрос звучит: для какого МИНИМАЛЬНОГО числа интегралов МОГЛА возникнуть такая ситуация.
Не требуется получить универсальный ответ в общем виде.
Для 5 интегралов такая ситуация вполне могла возникнуть. ( без всяких пустых множеств)

[Alexandroppolus]

SunTechnik,

Если 5-ка пустое множеств ( студентов меньше 5) и все интегралы решены, то они будут решены и для 4-ки студентов, что пртиворечит условию.

если студентов четверо, то нужен только один интеграл (он будет не решен всеми), тогда для единственной четверки условие выполняется, а для "всех пятерок" (коих 0 штук) оно выполняется автоматически в соответствии с Vacuous_truth.

если менее 4 студентов, то у нас 0 пятерок и четверок, и теперь оба условия выполняются всегда. Хотя при этом так же выполняются и условия "каждая четверка решила всё" и "каждая пятерка решила не всё", но они не противоречат условиям задачи.

так что если нужен только "самый-самый" минимум (если мы вправе выбрать число студентов), то мой ответ - 0 интегралов, при менее чем 4 студентах, и задача никак не относится к комбинаторике, а только лишь к логике.

[SunTechnik]

Alexandroppolus,

Читаем условие: "Любые четыре человека вместе нашли не все интегралы".

Если интеграл один, и его хоть кто-то решил, то условие уже не выполняется.

Но у Вас, судя по всему, своя логика...

[Alexandroppolus]

SunTechnik,

Если интеграл один, и его хоть кто-то решил

на всякий: у меня ответ "один интеграл" предусмотрен только для кейса, когда студентов всего четверо, причем этот интеграл никем не решен.

[Михаил Ливач]

Alexandroppolus, если студентов всего четверо, один интеграл, и его никто не решил, то у вас в любом случае не выполняется условие "пять студентов решили все интегралы", потому что множество комбинаций из пяти студентов пусто. Если вы не можете предъявить хотя бы один набор из 5 студентов, которые решили все интегралы, вы не можете утверждать, что условие выполнено.

[Alexandroppolus]

Михаил Ливач, вы смотрели по ссылке, которую я привел вчера?

[Михаил Ливач]

Alexandroppolus, посмотрел. В рамках текущей задачи, применяя этот подход, можно заявлять об одновременной истинности утверждений "все пятёрки студентов не нашли всех интегралов" и "все пятёрки студентов нашли все интегралы". А они взаимоисключающие. Если однозначно говорить об истинности или ложности какого-то утверждения невозможно, то в рамках математики такой разговор бессмысленен.
Vacuous truth может быть полезен, как точка устранимого разрыва. А в рамках текущей задачи я не вижу для него места.

[Alexandroppolus]

Михаил Ливач,

В рамках текущей задачи, применяя этот подход, можно заявлять об одновременной истинности утверждений "все пятёрки студентов не нашли всех интегралов" и "все пятёрки студентов нашли все интегралы". А они взаимоисключающие

Vacuous truth всегда приводит к таким результатам, не только здесь. Вы либо согласны с этой концепцией, либо нет, но не выборочно.

Если однозначно говорить об истинности или ложности какого-то утверждения невозможно, то в рамках математики такой разговор бессмысленен

смотря что доказываем. Если квантор существования, то достаточно указать пример, а если квантор всеобщности, то достаточно отсутствия контрпримера.
Авторское условие задачи содержит только кванторы всеобщности, не вижу проблем применить здесь Vacuous truth.

--
в условии сказано, что каждый интеграл был решен, то есть вариант "4 студента, 1 (нерешенный) интеграл" тут не подходил, но "3 студента, 0 интегралов" всё ещё соответствует всем требованиям из условия.

[Михаил Ливач]

Alexandroppolus, окей, давайте тогда посмотрим на это с такой стороны:
для случая 4 студентов вы заявляете: утверждение "Любые пять человек нашли вместе все интегралы" истинно, так как множество "пять студентов" пусто. Допустим, что вы правы. Из этого утверждения следует, что утверждение "нет ни одного интеграла, не решённого хотя бы одним студентом" тоже должно быть истинным. Но оно ложно для любого ненулевого количества интегралов.

[Alexandroppolus]

Михаил Ливач, от случая 4 студентов я отказался в прошлом комментарии (см. после "- -"), ещё раз перечитав условие.

[Михаил Ливач]

Alexandroppolus, случай "3 студента, 0 интегралов" тоже не подходит. Так как:
во-первых, очевидна истинность утверждения "Любой из этих трёх студентов решил все интегралы". Тогда выражение "Любые четыре человека вместе нашли не все интегралы" не может быть истинным, так как из-за "любые" оно должно включать в себя и такие группы, в которые входит хотя бы один из обозначенных студентов.

[Alexandroppolus]

Михаил Ливач, любое утверждение про "любых 4 студентов", даже заведомо ложное само по себе, будет оставаться истинным, пока нет ни одной четверки. Вы, похоже, до сих пор не прониклись всесильностью "пустой истины".

[Михаил Ливач]

Alexandroppolus, а мне кажется, это вы не прониклись тем, как и когда надо применять этот инструмент. Еси есть оппонент, заинтересованный в признании ваших выводов ошибочными ( проверяющий ), пользоваться им надо с осторожностью.