2
$\begingroup$

To plant trees at the center of each small square in a 3 * 4 rectangular area, it is required that there should be no continuous number of three (or more) trees in three directions of Horizontal, vertical or diagonal, how many methods of planting tree are there in total?

enter image description here

1 means trees can be planted, 0 means trees can not be planted.

I found that there are 15 ways to solve this problem through the method of violent exhaustion by Mathematica, but I don't know how to solve this problem with the mathematical method, and how to do it?

$\endgroup$
9
  • 1
    $\begingroup$ This bears a lot of resemblance to a concept in combinatorics known as the "rook polynomial." If you look up and study its uses cases and the properties of the analogy derived, you might be able to develop something similar for this sort of problem. (Assuming one doesn't already exist. This problem is just similar, but not 100% the same.) $\endgroup$ Mar 14, 2020 at 5:40
  • 3
    $\begingroup$ Brute force (what I assume you mean when you say "violent exhaustion") is still mathematical. It might, however, not be fun, or interesting, or enlightening. $\endgroup$
    – Arthur
    Mar 14, 2020 at 5:50
  • 1
    $\begingroup$ @Please correct GrammarMistakes how many trees should be planted? I assume that if only one tree is planted then the number of methods is already 12, and 2 trees planted then $\binom{12}{2}$? $\endgroup$ Mar 14, 2020 at 9:57
  • 1
    $\begingroup$ I already knew it cannot be 8 trees or more and it can be calculated from 1 to 7. But I will need an emphasis in the question to do this. $\endgroup$ Mar 14, 2020 at 10:06
  • 1
    $\begingroup$ Can you wait a while I will type that in the answer? $\endgroup$ Mar 14, 2020 at 10:16

1 Answer 1

3
$\begingroup$

Some greetings

@Please correct GrammarMistakes, here is my solution to your problem. It may be a little bit of "manual labour", and I may assume that I will not be able to solve it had it not been for a $3 \times 4$ table, which is rather small. If you feel this solution is correct and helpful, vote it up. If I made a mistake somewhere, please comment down here.

Solution

First, I shall prove that there is no way to plant more than 7 trees. So we divide the field into 4 figures of size $1 \times 3$ as following

enter image description here

If there is 8 trees planted, each $1 \times 3$ figure must have one unit square removed. Otherwise there is a contradiction.

Now, looking at the 3 pieces of $1 \times 3$ on the left, it is easy to show that the unit-squares removed from each $1\times 3$ rectange must not share a column, otherwise there is a column with no squares removed. A contradiction

enter image description here

But then, the 2 green squares must also be "unplanted", which not possible since we must have 8 squares planted.

Hence, the number of planted squares must be less than or equal to 7.

Case I: Number of trees planted is/are 1 or 2

It is obvious that there is no way the conditions may be violated, so the easy answer to this case is $\binom {12}{1}$ + $\binom{12}{2} = 78$

Case II: The number of trees planted is 3

Then we have $\binom {12}{3} = 220 $ planting ways in total, but there are 4 ways for the trees to be in the same column, and 6 ways for the trees to be in the same row, and 4 ways for them to be in the same diagonal. Hence, the number of correct painting methods is: $206$ ways.

Case III: The number of trees planted is 4

The number of cases in total: $\binom {12}{4} =495$

The number of ways three trees happen to be on the same row, column or diagonal: 14 ways.

Each way, there is 9 ways to choose a square for the last plant.

But minus the case when 4 plants are on a row, since they had been eliminated twice.

Therefore, the number of schemes in total is: $495-14*9+3=372$

Case IV, V, VI, there are 5, 6, 7 trees to be planted

I am so sorry but this is too exhausting for me. I think the 7 trees case is easy due to my proof above. Please complete the other 2 cases.

Post script

Because we have proven the number of plants to be less than or equal to 7, I proceeded with this solution. However, I think apply the same strategy as I did during my calculations above, I think there is a direct way to solve this problem.

Other than this, I think this problem can never appear in a mathematical contest paper or which paper similar because it takes too much time to complete without the aid of computers and electronic calculation devices.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .