Задачка на комбинаторику (?)

Red_Fighter

Нашли школьную задачку - решили и все корректно доказали где-то за час, но решение получилось не слишком красивым и далековато лежащим от традиционных школьных методов, которые к 5 курсу подзабылись =)
Может, кому-то удастся найти короткое красивое решение?
Имеется клуб любителей какой-нибудть игры, в котором N человек (N-четное, >=4). Игроки тренируются - на каждой тренировке разбиваются на две равные команды и команды играют друг против друга. Какое минимальное количество игр надо сыграть, чтобы для любых двух игроков
1)Была игра, в которой они играют за одну команду,
2)Была игра, в которой они играют за разные команды?

blackout

Условия 1) и 2) должны выполняться одновременно или это две разные задачи?

Skilet3d

Видимо стоит добавить, что разбиение на команды всегда разное

toxin

Каждому человеку сопоставим вектор из 0 и 1. В позиции i будет стоять 0 если он в i-той тренировке играл за первую команду и 1 если за вторую. Теперь задача сводится к тому, чтобы закодировать людей так, чтобы никакие 2 кода не совпадали и не были противоположными. Понятно что за t игр можно закодировать [math]$2^{t-1}$[/math] людей и больше нельзя.

Red_Fighter

Извиняюсь за недостаточно полную формулировку.
Да, условия 1) и 2) должны выполняться одновременно
Разбиение всегда разное - игроки разбиваются так, чтобы минимизировать кол-во игр для выполнения условий.

toxin

Хотя тут есть паразитное условие, что количество ноликов и единичек в каждой позиции одинаково. Если N делится на 4 то можно использовать конструкции:
!v 0 1 0
v 0 1 1
v 1 0 0
!v 1 0 1
и
!v 0 0 0
v 0 0 1
v 1 1 0
!v 1 1 1

incwizitor

1)Была игра, в которой они играют за одну команду,
N = 2 * k
ну если в лоб, то получаю достаточно [math]$$3 + (k\mod 2)$$[/math] игр (то есть не более 4)
алгоритм:
1) делим как угодно по k человек
2) из 1) обменять всех четных чувачков из обеих команд
3) из 1) всех четных чувачков в одну команду, нечетных в другую (тут важна четность k). если k нечетно, то будет один нечетный чувачок в разных командах
4) если k нечетно, то двух нечетных чувачков из 3) надо поменять местами
возможно, что-то забыл=\
пункт 2) исходной задачи пока не осилил, ибо не осознал, чем он отличается от 1) =\

Damrad

не катит. все нечетные игроки из первой команды никогда не сыграют против друг друга :(
у меня тоже изначально сложилось ощущение, что количество игр будет логарифм

incwizitor

все нечетные игроки из первой команды никогда не сыграют против друг друга
я решал первую подзадачу
логарифм во второй подзадаче возможен

Damrad

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

incwizitor

нужно решать обе сразу
прокосячил :o
Оставить комментарий
Имя или ник:
Комментарий: