일단 upper bound를 구할거임

46개중에 6개조합을 뽚는데 임의의3개 조합이 들어있어야한다 치자

다음과 같이 생각해볼수있음




일단 3개씩 뽑아서 46C3개의 조합을 만듬

그리고 얘네를 두개씩 이어붙여서 46C3 / 2 개의 조합을 만듬

이러면 최대 46C3 / 2 개의 조합안에 무조건 임의의 3개 조합이 포함됨






이제 다음 사실에 주목해보자

3개짜리 조합 46C3 개를 두개씩 이어붙이는데

한번 이어붙일때마다 새로운 조합들이 이어붙인 조합 내부에 생겨남

예를들어 123이랑 456을 이어붙이면 124, 125, 126 ...등의 새로운 조합이 내부에 생겨남

이렇게 생겨나는 내부의 조합을

처음에 구해놨던 46C3개의 3개짜리 조합에서

지워나갈꺼임




최대 몇개의 내부 조합이 생겨날까?

이어붙이는 두 3개짜리 조합에 중복되는 숫자가 하나도 없으면

6C3 - 2개만큼의 내부조합이 생겨남

그렇다면 과연 계속해서

중복되는 숫자가 하나도 없게 두개씩 이어붙여나갈수있을까?


임의의 조합 abc와 def를 이어붙였다고 치자

그러면 새로 생기는 조합들은

abd, cef, ...등등인데

이 새로 생기는 조합들은

무조건 서로 중복되는 숫자가 없게 짝을 지을수있음

abd cef 이런식으로


따라서 최초의 3개짜리 조합 집합이 중복되는 숫자가 없게 둘씩 짝을 지을수있었다면

거기서 임의의 두 조합을 이어붙인뒤 거기서 생겨나는 파생 조합들을 지운 새로운 집합도
중복되는 숫자가 없게 둘씩 짝지을수있음



따라서 새로운 upper bound는

46C3 / 6C3
= 759


이제 이게 lower bound임을 증명하기만하면됨