There are $m$ villages on the left bank of the Lena, $n$ villages on the right bank and one village on an island. It is known that $(m+1,n+1)>1$. Every two villages separated by water are connected by ferry with positive integral number. The inhabitants of each village say that all the ferries operating in their village have different numbers and these numbers form a segment of the series of the integers. Prove that at least some of them are wrong. (K. Kokhas)
Problem
Source: Tuymaada 2014, Day 2, Problem 4, Junior League
Tags: combinatorics unsolved, combinatorics, Tuymaada
don2001
05.03.2016 11:02
Does anyone have an idea on this problem ?
don2001
06.03.2016 13:44
Help me please ...
liberator
06.03.2016 15:31
Consider a graph $G=K_{m,n}\cup\{x\}$, consisting of a complete bipartite graph, with bipartition $\{L,R\}$ such that $|L|=m,|R|=n$, and a vertex $x$ connected to all other vertices, with $\gcd(m+1,n+1)>1$. The edges are labelled in $\mathbb{Z}$, and the claim is that for every vertex, incident edge labels form a sequence of consecutive integers. Disprove this claim. Suppose the claim holds. For a vertex $v$, let $S(v)$ be the set of edge labels incident to $v$. WLOG, let $S(x)=\{1,2,\dots,m+n\}$. Let $d=\gcd(m+1,n+1)$, and denote $D(v):=\{\ell\in S(v):d\mid\ell\}$. Now $$|D(v)|=\left. \begin{cases}\frac{n+1}{d}\;\forall v\in L\\ \frac{m+1}{d}\;\forall v\in R\\ \left\lfloor\frac{m+n}{d}\right\rfloor\text{ if }v=x\end{cases}\right\|\implies\sum_{v\in G}|D(v)|=\sum_{v\in L}|D(v)|+\sum_{v\in R}|D(v)|+|D(x)|=2\frac{(m+1)(n+1)}{d}-1,$$since $|D(x)|=\left\lfloor\frac{m+n}{d}\right\rfloor=\frac{m+1}{d}+\frac{n+1}{d}-1$. But as each edge is counted twice, the sum must be even, contradiction.
don2001
07.03.2016 05:40
I get it Thank you liberator for a nice solution
VMOer
16.06.2022 12:13
liberator wrote: Consider a graph $G=K_{m,n}\cup\{x\}$, consisting of a complete bipartite graph, with bipartition $\{L,R\}$ such that $|L|=m,|R|=n$, and a vertex $x$ connected to all other vertices, with $\gcd(m+1,n+1)>1$. The edges are labelled in $\mathbb{Z}$, and the claim is that for every vertex, incident edge labels form a sequence of consecutive integers. Disprove this claim. Suppose the claim holds. For a vertex $v$, let $S(v)$ be the set of edge labels incident to $v$. WLOG, let $S(x)=\{1,2,\dots,m+n\}$. Let $d=\gcd(m+1,n+1)$, and denote $D(v):=\{\ell\in S(v):d\mid\ell\}$. Now $$|D(v)|=\left. \begin{cases}\frac{n+1}{d}\;\forall v\in L\\ \frac{m+1}{d}\;\forall v\in R\\ \left\lfloor\frac{m+n}{d}\right\rfloor\text{ if }v=x\end{cases}\right\|\implies\sum_{v\in G}|D(v)|=\sum_{v\in L}|D(v)|+\sum_{v\in R}|D(v)|+|D(x)|=2\frac{(m+1)(n+1)}{d}-1,$$since $|D(x)|=\left\lfloor\frac{m+n}{d}\right\rfloor=\frac{m+1}{d}+\frac{n+1}{d}-1$. But as each edge is counted twice, the sum must be even, contradiction.