Задача из теории графов

[Stensen]

Доброго всем времени суток. Уважаемые, помогите разобраться.
Задача: Из десяти стран четыре подписали договор о дружбе ровно с пятью другими странами, а каждая из оставшихся шести — ровно с тремя. Сколько всего было подписано договоров?

Авторское решение (дословно): Четыре страны поставили $4 \cdot 5 = 20$ подписей. А оставшиеся шесть стран поставили $6 \cdot 3 = 18$ подписей. Ясно, что договоров в два раза меньше, чем общее количество подписей, то есть всего было подписано $\frac{20 + 18}{2}= 19$ договоров.

Примечание автора:
Неискушенный читатель может предложить неправильное решение: 4 страны подписали договор с 5-ю странами, всего 20 договоров; 6 стран с ещё 3-мя странами — ещё 18 договоров. Итого 38 договоров. Ошибка в данном рассуждении состоит в следующем: наборы $4 + 5$ и $6 + 3$ зависимы: «3 страны» из второго набора это какие-то из стран, уже учтенных в первом наборе. Отметим также, что при некоторых числовых данных условие задачи невыполнимо.

Похоже, я не понимаю условия (и авторского решения). Из решения следует, что 4 страны (каждая) поставили $4 \cdot 5 = 20$ подписей с пятью другими, т.е. заключили 20 договоров. Если на этом остановиться, то заключено 20 договоров.
Если подсчитать количество подписей, которые поставили оставшиеся 6 стран с 3-мя другими, то среди них, ввиду вовлечения всего набора стран в договорную деятельность, найдутся такие, с которыми уже заключены договоры с первой четверкой. Здесь непонятно:
1. среди оставшихся шести стран присутствуют те пять, с которыми заключены договоры с первой четверкой, т.е. из этих 6-ти стран, заключивших договоры, должно быть никак не меньше 5-ти, заключивших договоры с первой четверкой, т.е. 4, но не 3.
2.если 20 договоров уже есть, почему после окончательного расчета их оказалось 19?
Или условие нужно декодировать по другому?

[Null]

Stensen в сообщении #1632779 писал(а):

Или условие нужно декодировать по другому?

1 договор подписывают ровно 2 страны.

[Stensen]

Null в сообщении #1632787 писал(а):

Stensen в сообщении #1632779 писал(а):

Или условие нужно декодировать по другому?

1 договор подписывают ровно 2 страны.

Так, вроде, если 4 страны заключили договоры с 5-ю странами, то всего было поставлено $20+20=40$ подписей, а договоров в 2 раза меньше. Так и получается, что 2 страны на один договор.

[Null]

Stensen в сообщении #1632788 писал(а):

то всего было поставлено $20+20=40$ подписей,

Это не правда. Докажите.

[Stensen]

Null в сообщении #1632794 писал(а):

Stensen в сообщении #1632788 писал(а):

то всего было поставлено $20+20=40$ подписей,

Это не правда. Докажите.

Каждая из 4-х стран поставила подпись на договорах 5-ти стран, с которыми заключила договор. Всего эти 4 страны поставили 20 подписей. На этих договорах по 2 подписи, всего -40, а договоров-20.

[mihaild]

Stensen в сообщении #1632796 писал(а):

Всего эти 4 страны поставили 20 подписей. На этих договорах по 2 подписи, всего -40, а договоров-20

Есть 4 страны на Венере и 6 на Марсе. Каждая страна на Венере заключила договор с 5 странами. Венерианских подписей всего 20.
Но на некоторых договорах две венерианских подписи, поэтому нельзя сказать, что марсианских тоже 20.

[Null]

Stensen в сообщении #1632796 писал(а):

На этих договорах по 2 подписи

Почему эти договоры разные, и почему нет других?

[Stensen]

Я полагал, что по условию есть 2 группы: четверка и пятерка стран, каждая страна из четверки заключила договор с каждой страной из пятерки, тогда всего 20 договоров. Но если полагать, что 4 страны из 10-ти заключили договоры с любыми 5-тью из этой 10-ки, и еще с тремя оставшиеся 6, тем самым намекая, что задействованы все страны, то тогда понятно, все страны учтены дважды.
Условие я понимал так, видимо неверно.

[svv]

Stensen в сообщении #1632805 писал(а):

Я полагал, что по условию есть 2 группы: четверка и пятерка стран, каждая страна из четверки заключила договор с каждой страной из пятерки

Нет-нет, Четвёрка стран есть, а какой-то единой "пятёрки" нету. У каждой страны $a$ из Четвёрки — свой набор из 5 стран ("друзей $a$"), с которой $a$ заключила договор. Некоторые из "друзей $a$" могут входить в Четвёрку, некоторые не входят.

[Stensen]

Спасибо всем, пока понятно

[EUgeneUS]

Null в сообщении #1632787 писал(а):

1 договор подписывают ровно 2 страны.

Этого условия в задаче не хватает (оно предполагается неявно).

[svv]

Stensen
Три разных графа, удовлетворяющих условиям задачи.

Жёлтые — страны Четвёрки, у каждой 5 друзей.
Синие — страны Шестёрки, у каждой 3 друга.

Три варианта показывают различные соотношения "внутригрупповой" (между странами одного цвета) и "межгрупповой" (между странами разных цветов) дружбы. Слева максимальна межгрупповая дружба, справа максимальна внутригрупповая, посередине — промежуточный вариант.

[Stensen]

svv в сообщении #1632823 писал(а):

Stensen
Три разных графа, удовлетворяющих условиям задачи.

Жёлтые — страны Четвёрки, у каждой 5 друзей.
Синие — страны Шестёрки, у каждой 3 друга.

Три варианта показывают различные соотношения "внутригрупповой" (между странами одного цвета) и "межгрупповой" (между странами разных цветов) дружбы. Слева максимальна межгрупповая дружба, справа максимальна внутригрупповая, посередине — промежуточный вариант.

Спасибо, очень наглядно. Это какая-то программа делает или вручную?

[svv]

Stensen, это вручную (собственно рисование — CorelDraw). Но рисовалось легко и быстро, там куча вариантов.

[Alex Krylov]

Что-то вот такое возможно:

Используется синтаксис Matlab M

N = (10^2-10)/2;
A = zeros(11,N+1);
s = [5;5;5;5;3;3;3;3;3;3;0];

for i = 1:10    
    for j =1:10
        
        if (i~=j)
        q = max(i,j);
        k = min(i,j);
        ind = (q^2-3*q)/2+k+1;
        A(j,ind)=1;
        end
    end
end

A(11,1:N)=-1;
A(11,end)=1;

sol=pinv(A)*s;
sol(end)

Ответ: 19