Competition problem — Combinatorics

Library / /38 of 45

Combinatorics Difficulty 6.8 National olympiad Prove it Ukraine

Consider a complete graph with 4046 vertices with edges colored in some colors. We call a graph $k$ -good graph if all the vertices of the graph can be divided into 2023 pairs in such a way that among the colors of the 2023 of the edges connecting the vertices in the pairs are exactly $k$ distinct colors. Is it possible that the graph is 999-good and 1001-good, but not 1000-good?

(Anton Trygub)

Solution

Number the vertices of the graph with numbers from 1 to 4046. Consider the following graph: all edges between vertices of different parity are colored 1 and all other edges are colored in their unique colors. Consider any partition of the vertices into 2023 into pairs. Suppose that in $x$ of these pairs the vertices have different parity, and in $(2023 - x)$ the same.

Note that $(2023 - x)$ is an even number, because even numbers that are not in $x$ pairs where the numbers are of different parity must be paired with each other. Thus, $x$ is odd, and we have at least one edge of color 1 we have. Thus, the total number of different colors is
$1_{\{\text{first color}\}} + (2023 - x)_{\{\text{different colors in pairs with same parity}\}} = 2024 - x,$
is an odd number, i.e. we cannot get exactly 1000 colors.

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.