Задача на, видимо, комбинаторику, хотя не уверен

Принцип дерихле?

(C из (m-n) по k) + 1, не?

Только хотел спросить, почему k+1, как ты пофиксил :)

Ну во первых n > m, но если допустить что ты просто перепутал m и n местами, то получается что k не может быть больше (n-m), что вообще говоря не верно. Допускается вариант что вообще n=m.

Да, перепутал.

При m=n и k>(n-m) задача тривиальна.

n = 5, m = 3, k = 2

C из 2 по 2 = 1, +1 = 2. Пять элементов ну никак не покрыть двумя парами чтобы в выборке из трех была как минимум одна.

k * C(n, m) / n

А это число вообще не всегда целое. Для n=6 m=3 k=2 например дает 20/3.

И правда, подумаю еще

Придумал такой алгоритм: разбиваем множество на m-k+1 равных подмножеств (если n делится на m-k+1; если нет, то почти равных, но для упрощения формулы мы в дальнейшем будем считать что делится). В каждом подмножестве трахаем элементы по принципу «все со всеми». Так как мы не можем выбрать m элементов так, чтобы хотя бы k элементов не оказалось из одного подмножества, то у нас всегда будет как минимум одно совпадение.

Итого ответ: C((n/(m-k+1),k)*(m-k+1).

Кто меньше? (а я спать)

если в произвольном выборке (m) должно быть всё подмножество k элементов, тогда получается больше:
для пар получается - (C из (n-m) по 2) + (n-m)*m + 1

Если обобщать, для k=3:
(C из (n-m) по 3) + (C из (n-m) по 2)*m + (n-m)*(C из m по 2) + 1

в итоге:
[сумма (C из (n-m) по i) * (C из m по (k-i))] + 1
где i от 1 до k

А, так тебе нужно, чтобы оба элемента пары попадали в эту выборку, или хотя бы один? Если оба, то попробуй так:

(C из (n-m+k-1) по k) + 1.

Мы выбираем произвольное подмножество размера m, и считаем, сколько нужно пар, чтобы заполнить всё остальное. И берём на одну больше, чтобы уж точно хватило.

Или так.

для пар получается - (C из (n-m) по 2) + (n-m)*m + 1

Я вручную попытался решить вариант n=6 m=3 k=2, и обошелся шестью парами. По твоей формуле получается

С(3,2) = 3; +3*3+1 = 13. Вдвое больше.

Pythagoras

(C из (n-m+k-1) по k) + 1

C(4,2) = 6; +1 = 7. Опять же больше шести.

Точное решение пока некогда искать, оценочное: пар будет не больше чем нижняя грань C(n, m)/[C(n-k, m-k) - k + 1]

А может там просто С()-1 в знаменателе...

6 мало. Контрпример:

Пары: (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 2)

M: (4, 5, 6).

Кстати, 7 тоже мало. Полагаю, TheAnonymous прав.

6 мало.

(1,2)(1,3)(2,3)(4,5)(5,6)(4,6)

Ясно, я неправильно условие прочитал, подумал, что пары случайные

Вопрос же про «минимальное количество пар». Как его можно неправильно понять?

Я понял, как «какое минимальное количество произвольных пар нужно взять, чтобы в некотором подмножестве точно оказалась хотя бы одна из них»

Надо точнее условия формулировать, а то мы тут немного другую задачу решаем)

Если пары произвольные, то ничто не мешает им повторяться. Возьми хоть миллион пар (1,2)(1,2)(1,2)... и ты не покроешь даже множество из четырех элементов.

Требование неповторяемости совершенно естественно для подобной задачи.