5

Part of 1999 IMC

Problems(2)

Source: IMC 1999 day 1 problem 5

2n

n\times n

grid are marked. Show that for some

k > 1

2k

distinct marked points, say

a_1,...,a_{2k}

a_{2i-1}

a_{2i}

are in the same row,

a_{2i}

a_{2i+1}

are in the same column,

\forall i

, indices taken mod 2n.

graph theorylinear algebralinear algebra unsolved

IMC 1999 Problem 11

Source: IMC 1999 Day 2 Problem 5

S

be the set of words made from the letters

a,b

c

. The equivalence relation

\sim

S

uu \sim u

u \sim v \Rightarrow uw \sim vw \; \text{and} \; wu \sim wv

u, v

w

. Prove that every word in

S

is equivalent to a word of length

\leq 8