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

[Laguna]

Доброго времени суток, господа! Недавно столкнулся со следующей задачей:
"У нас есть упорядоченные кортежи из 3-х элементов, каждый элемент кортежа может принимать значение от 0 до 7. Примеры возможных кортежей(все они попарно РАЗЛИЧНЫ):
$(0, 0, 1), (1, 0, 0), (0, 0, 7), (2, 7, 7)$
Требуется определить какое максимально возможное число таких кортежей мы можем НАБРАТЬ, чтобы для любой пары из нашего НАБОРА количество совпадающих элементов на одинаковых позициях было не более одного"
Честно говоря, вообще никаких содержательный идей в голову не приходит. Знаю, что всего таких кортежей $8^3$. Также была мысль, что эту задачу можно решить кодом, потому что здесь есть явная монотонность по ответу(Если можно набрать n таких кортежей, то можно и n-1), применив бинарный поиск. Но чтобы это реализовать, надо уметь отвечать на вопрос "Можно ли собрать ровно n таких кортежей?",а я не знаю, как на него отвечать. Вообщем, прошу помощи

[mihaild]

Докажите, что по первым двум числам элемента НАБОРА восстанавливается третье. Получите из этого верхнюю оценку на размер НАБОРА.
Докажите, что она достигается - что существует НАБОР, в котором первые два числа могут быть произвольными.

[Laguna]

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

Докажите, что по первым двум числам элемента НАБОРА восстанавливается третье.

Не пойму, как это доказать. Ну есть у меня кортеж, первые 2 элемента которого, к примеру, равны 1 и 2, а как третье-то восстанавливается.
КАПСОМ ВЫДЕЛИЛ, ЧТОБЫ ЧИТАЮЩИЕ БОЛЕЕ ЧЕТКО ПОНЯЛИ ЗАДАЧУ

[mihaild]

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

Ну есть у меня кортеж, первые 2 элемента которого, к примеру, равны 1 и 2, а как третье-то восстанавливается

Ну естестевенно без знания набора не восстанавливается.
Более точно: докажите, что в любом подходящем наборе, если у двух кортежей совпадают первые два элемента, то совпадает и третий.

[Laguna]

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

если у двух кортежей совпадают первые два элемента, то совпадает и третий.

Такого вообще быть не может, по условию в наборе любые 2 кортежа имеют совпадения не более, чем в одном месте

[mihaild]

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

Такого вообще быть не может, по условию в наборе любые 2 кортежа имеют совпадения не более, чем в одном месте

Может, конечно - если это один и тот же кортеж.
Итого, если у нас есть набор, и два кортежа $a$ и $b$ из него, причем $a_1 = b_1$ и $a_2 = b_2$, то $a = b$. Что и означает, что если мы знаем $a_1$ и $a_2$, то мы знаем $a_3$.
Какое ограничение на количество кортежей из этого получается?

[Sender]

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

Ну есть у меня кортеж, первые 2 элемента которого, к примеру, равны 1 и 2, а как третье-то восстанавливается.

Кстати, есть довольно простой способ восстановления, по сути - построения искомого набора. Но сначала получите требуемые оценки.

[Laguna]

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

Итого, если у нас есть набор, и два кортежа $a$ и $b$ из него, причем $a_1 = b_1$ и $a_2 = b_2$, то $a = b$. Что и означает, что если мы знаем $a_1$ и $a_2$, то мы знаем $a_3$.

Честно говоря, вообще не понял вашего рассуждения. Опять же, если мы имеем 2 кортежа $a$ и $b$ из нашего набора, то у них не могут совпадать первые 2 элемента, т.е., к примеру, кортежей $(4,5,0)$ и $(4, 5, 2)$ в нашем наборе быть не может. Но ваш пример создает у меня в голове пример, как можно построить такой набор. Метод построения следующий:
Выпишем всевозможные кортежи (их $8^3$), затем делаем такой алгоритм: 1) Находим какие-то 2 кортежа, у которых есть совпадение по каким-то 2-м элементам 2) убираем какой-то один кортеж из этих 2-х 3) Если все оставшиеся кортежи в наборе удовлетворяют условию задачи, то останавливаемся, иначе возвращаемся к шагу 1)

[Sender]

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

Выпишем всевозможные кортежи (их $8^3$), затем делаем такой алгоритм

Нет гарантии, что ваш алгоритм оставит максимальный по количеству элементов набор.

[Laguna]

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

Нет гарантии, что ваш алгоритм оставит максимальный по количеству элементов набор.

Да, я понимаю. Я когда писал, держал это в голове и хотел это сказать, но забыл

[Sender]

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

т.е., к примеру, кортежей $(4,5,0)$ и $(4, 5, 2)$ в нашем наборе быть не может.

Сколько в одном наборе может быть кортежей вида $(4,5,x)$, где $x$ произвольное?

[mihaild]

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

Опять же, если мы имеем 2 кортежа $a$ и $b$ из нашего набора, то у них не могут совпадать первые 2 элемента, т.е., к примеру, кортежей $(4,5,0)$ и $(4, 5, 2)$ в нашем наборе быть не может

Да, не может.
Возможно Вам эта терминология еще непривычна, но когда мы говорим "возьмем два кортежа из набора" - это не означает, что кортежи различны, может быть два раза взять один и тот же.

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

[Laguna]

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

Сколько в одном наборе может быть кортежей вида $(4,5,x)$, где $x$ произвольное?

Только один

[Sender]

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

Только один

Правильно. mihaild по сути говорит вам, как это доказать строгим рассуждением.

[Laguna]

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

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

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