MathDB

distance between towns in country

Source: Mongolia MO 2000 Teachers P4

April 22, 2021

combinatorics

Problem Statement

In a country with

n

towns, the distance between the towns numbered

i

and

j

is denoted by

x_{ij}

. Suppose that the total length of every cyclic route which passes through every town exactly once is the same. Prove that there exist numbers

a_i,b_i

(

i=1,\ldots,n

) such that

x_{ij}=a_i+b_j

for all distinct

i,j