pigeon hole principle help! (1 Viewer)

[mathsbrain]

Consider a 3cmX3cm grid, made of nine 1X1cm squares.
If you are to put a stamp in the squares, what is the maximum number of stamps you can make without having 3 stamps diagonally, vertically or horizontally?
Obviously the answer is 6 by intuition, but how can you use pigeon hole principle to explain?

 

[InteGrand]

Consider a 3cmX3cm grid, made of nine 1X1cm squares.
If you are to put a stamp in the squares, what is the maximum number of stamps you can make without having 3 stamps diagonally, vertically or horizontally?
Obviously the answer is 6 by intuition, but how can you use pigeon hole principle to explain?

You can show that if there are 7 stamps placed, then there must be a row of 3 stamps as follows:

Suppose 7 stamps are placed, then consider the "blank" squares (squares that don't have a stamp in them). There are 2 blank squares (because there are 7 stamps placed in 9 squares). Since there are 3 rows and 2 blank squares, at most 2 rows can have a blank square in them, so there is at least 1 row with no non-blank squares, i.e. a row with 3 stamps.

 

[mathsbrain]

You can show that if there are 7 stamps placed, then there must be a row of 3 stamps as follows:

Suppose 7 stamps are placed, then consider the "blank" squares (squares that don't have a stamp in them). There are 2 blank squares (because there are 7 stamps placed in 9 squares). Since there are 3 rows and 2 blank squares, at most 2 rows can have a blank square in them, so there is at least 1 row with no non-blank squares, i.e. a row with 3 stamps.

But according to my school, we need to identify what are the pigeons and the pigeon holes in every problem, and there must be more pigeons than pigeon holes for PHP to work, can you elaborate please?

 

[vinlatte]

Consider a 3cmX3cm grid, made of nine 1X1cm squares.
If you are to put a stamp in the squares, what is the maximum number of stamps you can make without having 3 stamps diagonally, vertically or horizontally?
Obviously the answer is 6 by intuition, but how can you use pigeon hole principle to explain?

I read the Maths in Focus textbook since they had an example that is similar to your grid question.

Since it is a 3x3 grid and you are finding when it does make a line of 3, 3 is your pigeonhole number. There are a total of 9 stamp placements, these are your pigeons.

To make it easier to visualise, a 3x3 grid has 3 rows. In each row, you can put 1 or 2 stamps but 3 stamps will result in a row of 3. So the maximum number of stamps per row is 2. For the total grid, the maximum number of stamps will be 2 multiply the number of rows (3) which equals 6.

This will be arranged as all the squares stamped except a diagonal line.

 

[mathsbrain]

I read the Maths in Focus textbook since they had an example that is similar to your grid question.

Since it is a 3x3 grid and you are finding when it does make a line of 3, 3 is your pigeonhole number. There are a total of 9 stamp placements, these are your pigeons.

To make it easier to visualise, a 3x3 grid has 3 rows. In each row, you can put 1 or 2 stamps but 3 stamps will result in a row of 3. So the maximum number of stamps per row is 2. For the total grid, the maximum number of stamps will be 2 multiply the number of rows (3) which equals 6.

This will be arranged as all the squares stamped except a diagonal line.

Hmm, i don't quite get this...
PHP says if you have more holes than pigeons, then there is at least one hole with more than 1 pigeon.
You have 9 pigeons(stamps) and 3 holes(line of 3), so there is at least one hole with more than 1 stamp, which has no relation to the question for the following reasons:
1) each hole can only have 0 or 1 stamp, not more than 1
2) question wants a maximum of 2 stamps in 3 holes vertically, horizontally or diagonally
Hmm...i am not sure if i am missing something but this doesn't look like it works?

 

[vinlatte]

Hmm, i don't quite get this...
PHP says if you have more holes than pigeons, then there is at least one hole with more than 1 pigeon.
You have 9 pigeons(stamps) and 3 holes(line of 3), so there is at least one hole with more than 1 stamp, which has no relation to the question for the following reasons:
1) each hole can only have 0 or 1 stamp, not more than 1
2) question wants a maximum of 2 stamps in 3 holes vertically, horizontally or diagonally
Hmm...i am not sure if i am missing something but this doesn't look like it works?

It's not a usual pigeonhole question, that's why it is difficult to explain. It's mostly picking items, like a deck of cards, socks, things you would usually see in a probability type question.

It's actually the other way around: more pigeons than pigeonholes means there is at least hole with more than one pigeon.

The rule: If there are (n+1) pigeons and n holes, there is at least 2 pigeons in one hole.

I didn't explain it clearly, there are 3 rows (pigeonholes) that can have 2 stamps each; but on the 7th stamp (pigeon), there will be a row of 3, either diagonally, vertically or horizontally. So 6 stamps (2 per row) is the maximum amount of stamps that doesn't form a 3 in a row on the grid.