Задача о женихах и невестах

Форум для обсуждения вопросов математики

Модератор: Admin

Космонаут
Сообщения: 3
Зарегистрирован: Ср ноя 10, 2010 9:17 am

Задача о женихах и невестах

Сообщение Космонаут » Ср ноя 10, 2010 9:32 am

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

nataly-mak
Сообщения: 29
Зарегистрирован: Вс авг 17, 2008 5:45 pm
Контактная информация:

Сообщение nataly-mak » Ср ноя 10, 2010 9:37 am

А какая задача-то? :)
Лучше один раз увидеть...

Космонаут
Сообщения: 3
Зарегистрирован: Ср ноя 10, 2010 9:17 am

Сообщение Космонаут » Ср ноя 10, 2010 10:12 am

Даны два пронумерованных набора чисел

a1,a1,...,an и b1,b2,...,bn (n,m => 2)

удовлетворяющих неравенствам 0<=ak<=k (k:1<=k<=n) и 0<=bl<=l (l: 1<=bl<=m).

Кроме того для всех наборов имеются "краевые" условия:
an = n, bm = m, a1 + b1 = 1.

Доказать( или опровергнуть), что найдется пара номеров
K, L ( 1<=K<=n, 1<=L<=m), таких что сумма s = K + L этих номеров удовлетворяет условиям 2 < s < (m + n)

и для всех остальных пар (ak, bl) с той же суммой номеров k + l = s выполняется неравенство aK + bL < ak + bl.

Другими словами найдется набор чисел
Gs = {((ak + bl) | k + l = s, 3 <=s<=(m+n - 1)}
с единственным минимумом входящих в этот набор сумм


Комбинаторика :)

Космонаут
Сообщения: 3
Зарегистрирован: Ср ноя 10, 2010 9:17 am

Сообщение Космонаут » Ср ноя 10, 2010 10:13 am

Я планирую разобрать пока только для частного случая n,m = 2