MathDB

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

3

, 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

11

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

2^{10}-11

avengers in the agency.
This problem is adapted from 2015 IMO Shortlist C7.

Problem Statement