# graph question

#### MichNugget

The Mathematical Forest is grown in a two-dimensional plane, where trees can only grow on
points with integer coordinates. To start with, there are no trees at all. The foresters plant
the first tree at (0; 0). Each year, they carry out tree planting according to the following
rule. If there is a tree on the point (m; n) but there are no trees on the points (m+1; n) and
(m; n + 1), then they can choose to remove the tree on (m; n) and plant new trees on the
points (m; n + 1) and (m + 1; n).
For an integer k >= 1, the kth diagonal consists of all points (m; n) with m + n = k - 1. Is
it possible for the foresters to arrange their planting so that eventually there are no trees on
the first 2 diagonals? What about the first 3 diagonals? 4 diagonals? Can you generalize?

#### skipjack

Forum Staff
How many trees are there on the first 3 diagonals after the first tree is planted?

Also, where did you copy this question from?

#### MichNugget

This problem I saw on another math forum and chegg
there are 6 trees on the first 3 diagonals
— 1+2+3

#### skipjack

Forum Staff
You can't rely on such sources.

How can there be 6 trees immediately after just one tree has been planted?

#### MichNugget

yeah my bad first there will be 1 at the first diagonal 0,0 then 2 on the second diagonal 0,1 and 1,0 and then there will be 3 on the third diagonal 2,0 2,2 and 0,2

#### skipjack

Forum Staff
. . . first there will be 1 at the first diagonal 0,0
That's correct. The problem features the wording "they can choose to remove the tree on (m; n)". They may choose to remove some tree, subject to the specified condition, but they aren't required to remove any tree. Immediately after the first tree is planted, there are, by definition, no trees planted on the second and third diagonals.

. . . then 2 on the second diagonal 0,1 and 1,0
In order to clear the first diagonal, the point (0, 0), they can choose to remove the tree that's there initially, and, to comply with the rules, plant trees on the points (0, 1) and (1, 0). There are then no trees on any diagonals other than the second diagonal.

. . . then there will be 3 on the third diagonal 2,0 2,2 and 0,2
That wouldn't comply with the rules. They can choose to remove a tree, but removing two trees simultaneously isn't an operation covered by the rules.

Each tree removal is accompanied by two trees being planted, so the nth removal and planting step results in exactly n trees in the forest. What progress can you now make?