Вроде простая задачка по комбинаторике

[mihaild]

Laguna в сообщении #1638600 писал(а):

Из ваших рассуждения следует, что размер набора не больше 8?

Почему 8-то?

[Laguna]

mihaild в сообщении #1638601 писал(а):

Почему 8-то?

Блин, тогда я пока вообще не пойму ваши рассуждения. Ну, пусть у меня первые 2 элемента кортежа, к примеру, будут два нуля, если третий элемент, как вы утверждаете, определяется однозначно, то какой он тогда в моем случае будет?

-- 10.05.2024, 02:52 --

mihaild в сообщении #1638597 писал(а):

Важно, что если у нас есть набор, то кортеж из набора однозначно задается первыми двумя компонентами. Что из этого следует про размер набора?

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

[Sender]

Laguna в сообщении #1638602 писал(а):

Ну, пусть у меня первые 2 элемента кортежа, к примеру, будут два нуля, если третий элемент, как вы утверждаете, определяется однозначно, то какой он тогда в моем случае будет?

Зависит от конкретного набора: в одном наборе какой-то один, в другом - другой.

-- Пт май 10, 2024 10:12:15 --

Laguna в сообщении #1638602 писал(а):

Вот тут тоже не особо понимаю. Хорошо, пусть мы задали кортеж $(4, 5, x)$, он у нас, как вы говорите, такой один, потому что любой кортеж, дескать, задается первыми 2-мя элементами. А что тогда можно сказать про кортеж вида $(6, 5, x)$?

Давайте попробуем так. Допустим, в данном наборе третий элемент кортежа определяется по первым двум функцией $x_3=f(x_1,x_2)$. Допустим далее, что у нас в данном наборе имеется два кортежа $(4, 5, f(4,5))$ и $(6,5,f(6,5))$. Возможно ли, что $f(4,5)=f(6,5)$?

[mihaild]

Laguna в сообщении #1638602 писал(а):

Ну, пусть у меня первые 2 элемента кортежа, к примеру, будут два нуля, если третий элемент, как вы утверждаете, определяется однозначно, то какой он тогда в моем случае будет?

mihaild в сообщении #1638597 писал(а):

если у нас есть набор

Т.е. если Вы мне принесете набор, загадаете кортеж из него и скажете мне два первых элемента кортежа, то я смогу назвать Вам третий.

Laguna в сообщении #1638602 писал(а):

Вот мы его тоже задали 2-мя отличными от предыдущего кортежа элементами, однако у них теперь совпадают 2-й и 3-й элементы и они не подходят

Правильно, такое рассуждение даст нам только верхнюю оценку на размер набора, что она достигается, нужно будет проверять отдельно.

[Laguna]

Sender в сообщении #1638615 писал(а):

Возможно ли, что $f(4,5)=f(6,5)$?

Нет, ибо если бы был, то получилось бы 2 кортежа, у которых на 1-й и 3-й позиции стоят одинаковые элементы. Оценку на размер не вижу

-- 10.05.2024, 15:03 --

mihaild в сообщении #1638617 писал(а):

Т.е. если Вы мне принесете набор, загадаете кортеж из него и скажете мне два первых элемента кортежа, то я смогу назвать Вам третий.

Понял. 3-й элемент зависит от конкретного набора.

mihaild в сообщении #1638617 писал(а):

Правильно, такое рассуждение даст нам только верхнюю оценку на размер набора, что она достигается, нужно будет проверять отдельно.

Честно говоря, по-прежнему не вижу, где здесь может вылезти какая-то оценка

[mihaild]

Laguna в сообщении #1638628 писал(а):

Честно говоря, по-прежнему не вижу, где здесь может вылезти какая-то оценка

Вот у вас есть набор. И чтобы задать кортеж из него, достаточно знать два числа от 0 до 7 (первые два элемента кортежа). Сколько максимум элементов в наборе?

[Laguna]

mihaild в сообщении #1638629 писал(а):

Вот у вас есть набор. И чтобы задать кортеж из него, достаточно знать два числа от 0 до 7 (первые два элемента кортежа). Сколько максимум элементов в наборе?

64?

[mihaild]

Laguna в сообщении #1638630 писал(а):

64?

Почему 64-то?

[Laguna]

mihaild в сообщении #1638631 писал(а):

Почему 64-то?

Мы выбираем первый элемент 8-ю способами, второй элемент 8-ю способами, а 3-й определяется однозначно в каждом кортеже?

[mihaild]

Да, правильно.
Итак, не бывает наборов размера больше чем 64. Если мы найдем набор размера 64, то задача будет решена.
Предыдущие рассуждения говорят, что в наборе размера 64 встречаются все возможные комбинации первого и второго элементов. Таким образом, наша задача - придумать функцию $f(x, y)$, дающую третий элемент кортежа по двум первым таким образом, чтобы если $a \neq b$, то $f(x, a) \neq f(x, b)$ и аналогично $f(a, y) \neq f(b, y)$ (понятно ли, как из такой функции сделать нужный набор?).
Тут, в зависимости от Ваших знаний некоторых других разделов алгебры, Вам может быть проще или сложнее придумать такую функцию. Если не получается, то попробуйте рассмотреть случай, когда значения не от 0 до 8, а от 0 до 1 (т.е. у нас булева функция двух аргументов).