MathDB

13

Part of 1986 IMO Longlists

Problems(1)

f_ij for a set{1,2,3,...,n}

Source:

8/28/2010
Let N={1,2,…,n}N = \{1, 2, \ldots, n\}, n≥3n \geq 3. To each pair i≠ji \neq j of elements of NN there is assigned a number fij∈{0,1}f_{ij} \in \{0, 1\} such that fij+fji=1f_{ij} + f_{ji} = 1. Let r(i)=∑i≠jfijr(i)=\sum_{i \neq j} f_{ij}, and write M=max⁡i∈Nr(i)M = \max_{i\in N} r(i), m=min⁡i∈Nr(i)m = \min_{i\in N} r(i). Prove that for any w∈Nw \in N with r(w)=mr(w) = m there exist u,v∈Nu, v \in N such that r(u)=Mr(u) = M and fuvfvw=1f_{uv}f_{vw} = 1.
graph theoryalgebra proposedalgebra