MathDB

At an IMOTC party, all people have pairwise distinct ages. Some pairs of people are friends and friendship is mutual. Call a person junior if they are younger than all their friends, and senior if they are older than all their friends. A person with no friends is both junior and senior. A sequence of pairwise distinct people

A_1, \dots, A_m

is called photogenic if: 1.

A_1

is junior, 2.

A_m

is senior, and 3.

A_i

and

A_{i+1}

are friends, and

A_{i+1}

is older than

A_i

for all

1 \leq i \leq m-1

.
Let

k

be a positive integer such that for every photogenic sequence

A_1, \dots, A_m

m

is not divisible by

k

. Prove that the people at the party can be partitioned into

k

groups so that no two people in the same group are friends.
Proposed by Shantanu Nene

6

Problems(1)