MathDB

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

Source:

August 28, 2010

graph theoryalgebra proposedalgebra

Problem Statement

Let

N = \{1, 2, \ldots, n\}

,

n \geq 3

. To each pair

f_{ij} + f_{ji} = 1

of elements of

N

there is assigned a number

f_{ij} \in \{0, 1\}

such that

f_{ij} + f_{ji} = 1

. Let

r(i)=\sum_{i \neq j} f_{ij}

, and write

M = \max_{i\in N} r(i)

,

m = \min_{i\in N} r(i)

. Prove that for any

w \in N

with

r(w) = m

there exist

u, v \in N

such that

r(u) = M

and

f_{uv}f_{vw} = 1

.

Back to Problems View on AoPS