Proving Existence by Contradiction

Idea · Intermediate

Combinatorics

Proving existence by contradiction is a method used to show that at least one object or configuration satisfies a given property.

Instead of constructing such an object directly, we assume that no such object exists and show that this assumption leads to a contradiction.

A particularly useful technique is to consider all possible configurations, derive an inequality for each one, and add these inequalities to obtain a contradiction.

The distance between two permutations of the same length is defined as the number of positions at which their entries differ. For example, the distance between $\pi'=\langle 2,5,1,4,3\rangle$ and $\pi''=\langle 2,3,4,1,5\rangle$ is $4$ , since they differ at the second, third, fourth, and fifth positions.

Let $A$ be a set of $2026$ permutations of length $n$ , denoted by $\pi_1,\pi_2,\ldots,\pi_{2026}$ . The distance from a permutation $\pi$ of length $n$ to the set $A$ is defined as the sum of its distances to all the permutations in $A$ . Among all permutations of length $n$ , let $x$ be the minimum distance to $A$ . Prove that there exists a permutation in $A$ (one of the $\pi_i$ ) whose distance to $A$ is at most $2x$ .