MathDB

Show that there exists a function

Source: Turkish TST 2011 Problem 3

July 23, 2011

functionpigeonhole principlecombinatorics proposedcombinatorics

Problem Statement

Let

A

and

B

be sets with

2011^2

and

2010

elements, respectively. Show that there is a function

f:A \times A \to B

satisfying the condition

f(x,y)=f(y,x)

for all

(x,y) \in A \times A

such that for every function

g:A \to B

there exists

(a_1,a_2) \in A \times A

with

g(a_1)=f(a_1,a_2)=g(a_2)

and

a_1 \neq a_2.