# Grid problem

Printable View

• May 10th 2012, 12:32 PM
Tiome
Grid problem
hi, please help me on this problem, I have no idea how to start. thank you

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.
• May 10th 2012, 01:10 PM
Plato
Re: Grid problem
Quote:

Originally Posted by Tiome
hi, please help me on this problem, I have no idea how to start. thank you
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?
• May 10th 2012, 01:28 PM
Tiome
Re: Grid problem
I think this is a pigeon hole problem , order matters,and there are 32 squares on each side.
• May 10th 2012, 01:36 PM
emakarov
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?
• May 10th 2012, 01:51 PM
Plato
Re: Grid problem
Quote:

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?