MathDB

Maximal k such that an acceptable 2-coloring exists

Source:

February 11, 2006

geometryrectanglemodular arithmeticcombinatorics proposedcombinatorics

Problem Statement

Let

k

and

n

be positive integers. Consider an array of

2\left(2^n-1\right)

rows by

k

columns. A

2

-coloring of the elements of the array is said to be acceptable if any two columns agree on less than

2^n-1

entries on the same row. Given

n

, determine the maximum value of

k

for an acceptable

2

-coloring to exist.