On the football training there was $n$ footballers - forwards and goalkeepers. They made $k$ goals. Prove that main trainer can give for every footballer squad number from $1$ to $n$ such, that for every goal the difference between squad number of forward and squad number of goalkeeper is more than $n-k$. (S. Berlov)
Problem
Source: Tuymaada 2015, Day 1, Problem 1, Senior League
Tags: combinatorics, algebra
10.07.2017 12:51
It's enough to consider the case when each pair of forward and goalkeeper create at most one goal. Consider the relation as a bipartite simple graph with vertices from $F,G$ and each edge represent a goal. We've $|F|+|G|=n$ and the total number of edges is $k$. We'll prove that we can assign squad numbers that satisfy the condition and that vertex in $F$ get a squad number in $\{ 1,2,...,|F|\}$ and $G$ get one in $\{ n,n-1,...,n-|G|+1\}$ by induction on $n$. Suppose the statement is true for all $n\leq m$ where $m\in \mathbb{Z}^+$ When $n=m+1$. Note that we can swap the condition by setting squad numbers $f\rightarrow n+1-f,g\rightarrow n+1-g$ for $f\in F,g\in G$ If there's a vertex, WLOG in $F$, that no edge connect from it. Consider the graph without that vertex , by induction step, we have a set of squad numbers. Shift all squad number of every vertex in $G$ by one, and let that vertex be the rest squad number. Now, every vertex has degree at least one, we get $k\geq |F|,|G|$, so $n-k\leq |F|,|G|$. If there's a vertex, WLOG in $F$, with degree one. Consider the graph without that vertex and that edge, by induction step, we have a set of squad numbers. Shift all squad numbers of every vertex by one, and let that vertex be squad number $1$. Since every vertex in $G$ has squad number $\geq (m-|G|+1)+1=|F|+1$ and $n-k\leq |F|$, this satisfy the condition. Now, we have to complete the case when every vertex has degree at least two, so $k\geq n$, and so it's trivial.
29.01.2022 10:40
I have another solution Consider that n is fix we will prove the problem by induction on k . For k=1its true. Every time we add an adge and we show the statement will stay true. consider i>=j and the adge is between the ith forward and jth goal keeper now replacing the ith forward with i+1th forward or jth goalkeeper with j-1 th goalkeeper will do the job If we can't do that then it mean i-j=n-1 and we added the nth edge.
29.01.2022 19:03
It is equivalent to: $G$ is a bipartite graph with sides $X,Y$ (there is an edge between two vertices if and only if they are in different sides) and $|E(G)| \le k$. Degree of any vertice is at least 1. Prove that we can give one of the numbers $1,2,...,n$ to each vertex such that (condition:) "the difference between any two numbers on neighbouring vertices are at least $n-k$". Proof: Let $X=x_n,...,x_{(m+1)}$ with $d(x_i) \ge d(x_j) \iff i \ge j$. Let $S_i$ show the set of the vertices which is connected to $x_i$. We write its indice on each vertice in $X$. Note that $|S_{m+1} \cup S_{m+2} \cup ... \cup S_l| \le \frac{k(l-m)}{n-m}$. We have *$l-\frac{k(l-m)}{n-m} \ge n-k \iff (n-l)(m+k-n) \ge 0$ which is true. Now we write $1,2,...,d(x_{m+1}) \le \frac{k}{n-m}$ to the vertices in $S_{m+1}$ (these numbers satisy the condition as a result of *) and we write the least one which was not written on any vertice. Assume that we write a number on any vertice in $S_{m+1} \cup S_{m+2} \cup ... \cup S_{l-1}$ satisfying the condition. We can write at least $\frac{k(l-m)}{n-m}- |S_{m+1} \cup S_{m+2} \cup ... \cup S_{l-1}|\ge |S_{m+1} \cup S_{m+2} \cup ... \cup S_l|- |S_{m+1} \cup S_{m+2} \cup ... \cup S_{l-1}|$ numbers on vertices in $S_l$ but not in $S_{m+1} \cup S_{m+2} \cup ... \cup S_{l-1}$ and they satisfy the condition (as a result of *). $\square$