USAMO $1989$, 문제 $2$
문제 $2$ USAMO에서 $1989$: $20$ 지역 테니스 클럽의 회원들은 정확히 $14$2 인 게임, 각 구성원이 적어도 한 게임에서 플레이합니다. 이 일정 내에 6 개의 게임 세트가 있어야 함을 증명하십시오.$12$ 뚜렷한 플레이어.
솔루션에서 시도 내 : 있기 때문에$20$ 각 플레이어가 적어도 한 게임을 플레이 한 경우, 모든 플레이어를 수용하기 위해 구성해야하는 최소 경기 수는 $10$. 지금,$4$재생할 수 있습니다 남아있는 더 일치, 기껏해야 $8$ 이들의 $20$플레이어. 따라서 적어도 $12$ 플레이어의 $1$일치, 따라서 함께 6 개 경기의 세트가 존재한다$12$뚜렷한 선수 . 이것이 엄격한 증명의 원칙이 될 것이라고 믿습니다.
내 마음을 흐리게하는 다음과 같은 의심이 있습니다.
- 내 추론이 건전한가? 즉, 함정이 없는가?
- 맞다면 수학적으로 엄격한 증명에서 위의 추론을 어떻게 구성해야할까요?
편집 : Ben이 주석에서 지적했듯이 이탤릭체로 된 진술은 정당하지 않습니다. 이 증거를 짜는 동안 많은 가능성을 간과 한 것 같습니다. 따라서 보다 합리적인 증명을 진행하기 위해 몇 가지 힌트를 얻고 싶습니다.
답변
함정이있는 것이 두렵습니다. 정확히 1 게임을 플레이 한 사람들 중 12 명의 다른 플레이어가있는 6 개의 게임이 있음을 증명하려고하면 실패합니다. 예를 들면 다음과 같습니다.
$$ 1-2\\ 3-4\\ 5-6\\ 7-8\\ 9-10\\ 11-12\\ 12-13 \\ 13-14\\ 14-15\\ 15-16\\ 16-17\\ 17-18\\ 18-19\\ 19-20$$
12 명의 플레이어가있는 6 개의 게임이 있지만 정확히 1 개의 게임을 가진 플레이어 간에는 5 개의 게임 만 있습니다.
여기에 힌트가 있습니다. 플레이어를 두 그룹으로 나눕니다. 한 게임을 가진 그룹과 더 많은 그룹을 가진 그룹입니다. 그런 다음 플레이어를 한 게임으로 짝을 지어 플레이어를 한 게임에 짝을 지어 더 많은 플레이어와 마지막으로 더 많은 게임을 가진 플레이어를 연결합니다.
편집 : 두 번째 접근
모든 사람이 정점으로, 모든 게임이 가장자리로 간주된다면, 질문은 최소한 크기가 일치한다는 것을 증명하도록 요구합니다. $6$. 마찬가지로, 최대 매칭의 크기가$MM$ 적어도 크기입니다 $6$. 최대 일치는 정점을 두 세트로 분할합니다.$MM$, 크기 $2\cdot |MM|$, 크기가없는 것 $20 - 2\cdot |MM|$우리 문제를 위해. 모든 정점이 적어도$1$, 우리는 적어도 $20 - 2\cdot |MM|$두 파티션 사이의 가장자리. 지금,
$$ E_{MM} + E_{\text{between}} \le |E| = 14 \implies \\ |MM| + 20 - 2\cdot |MM| \le 14 \implies \\ |MM| \ge 6$$