MathDB

3

Part of 2016 Taiwan TST Round 3

Problems(1)

Avengers

Source: 2016 Taiwan TST Round 3, 2015 ISL C7

7/26/2016
You are responsible for arranging a banquet for an agency. In the agency, some pairs of agents are enemies. A group of agents are called avengers, if and only if the number of agents in the group is odd and at least 33, and it is possible to arrange all of them around a round table so that every two neighbors are enemies. You figure out a way to assign all agents to 1111 tables so that any two agents on the same tables are not enemies, and that’s the minimum number of tables you can get. Prove that there are at least 210−112^{10}-11 avengers in the agency.
This problem is adapted from 2015 IMO Shortlist C7.
combinatorics