1. ## Grid problem

A 64 x 64 grid is filled with 2 x 2 matrices. The four entries in each matrix are chosen without replacement from the set {a,b,c,d,e,f}. What is the least number of identical matrices guaranteed to appear in the grid? Justify your answer.

2. ## Re: Grid problem

Originally Posted by Tiome
A 64 x 64 grid is filled with 2 x 2 matrices. The four entries in each matrix are chosen without replacement from the set {a,b,c,d,e,f}. What is the least number of identical matrices guaranteed to appear in the grid? Justify your answer.
It is not at all clear how this grid is configured.
Does each square contain a $\displaystyle 2\times 2$ matrix so that is $\displaystyle 2^{12}$ matrices in total???

OR WHAT?

3. ## Re: Grid problem

I think this is a pigeon hole problem , order matters,and there are 32 squares on each side.

4. ## Re: Grid problem

Let n be the number of empty matrices on the grid, and let m be the number of all possible distinct matrices filled with elements of {a,b,c,d,e,f}. Find n and m.

This is a problem on the generalized pigeonhole principle. Here containers are distinct filled matrices, pigeons are initially empty matrices on the grid, and a pigeon (empty matrix) is in a container (filled matrix) if it is going to be filled that way. The link gives a formula for the minimum number of pigeons in a container.

An intuitive way to think about this is to consider the worst case, when as many matrices as possible are different. We fill the grid with filled matrices #1, #2, ..., #m, then again #1, #2, ..., #m and so on. How many such complete series of m matrices will be there and what about the remaining matrices?

5. ## Re: Grid problem

Originally Posted by Tiome
I think this is a pigeon hole problem , order matters,and there are 32 squares on each side.
The permutation of six letters taken 4 at a time is $\displaystyle _6\mathcal{P}_4=360$.
Now $\displaystyle 32\times 32=2^{10}$. SO?