# How do I find the maximum quantity of trees to be chopped in a field given a square?

The problem is as follows:

In a oasis, a lumberjack sees that a group of palm trees has a $$7\times 7$$ formation making a square as it is shown in the diagram from below. Find the maximum quantity of trees to be cut down by the lumberjack to get five different straight lines of four palm trees each. I found this in my riddles book and I don't know exactly what should I do to solve this problem.

The alternatives given are:

$$\begin{array}{ll} 1.&39\,\textrm{trees}\\ 2.&36\,\textrm{trees}\\ 3.&20\,\textrm{trees}\\ 4.&32\,\textrm{trees}\\ \end{array}$$

I'm confused exactly how should I understand the word maximum amount of trees?. What about straight lines, do diagonals count?.

I feel that if I select a group of trees in a diagonal for example, this pivot tree will include other lines as well, but that's where I'm stuck at.

If this is the case will this minimize the number of trees?. I'm slow at understanding these sorts of problems, therefore I'd really appreaciate if someone were to assist me with this, try to include some sketch or drawing explaining step-by-step the logic behind the solution of this riddle.

Thinking about this problem in reverse is easier, i.e. think about the trees that need to remain. Find the fewest number of trees that can be arranged in five lines with 4 trees in each line. To minimise that number, we need as many trees as possible to do double duty by being part of multiple lines.

If you have five straight lines, none of them parallel, then they all intersect each other. Each line cuts through the four others, so has four intersection points. There are 10 intersection points in total because any two lines intersect and there are 10 ways to choose two of the 5 lines. One such arrangement is a pentagram for example.
It turns out to be possible to find such an arrangement of 10 trees in five lines of four, which also lie within a 7x7 grid. So with 10 trees left, we have chopped down 49-10=39 trees.

It is difficult to find this arrangement. I approached it by first deciding on the slopes of the lines. The obvious directions are vertical, horizontal, and two diagonals. For the fifth direction you need to go a knights-move between points on the line, and this is rather restrictive as it spans the width or height of the grid.
You also need the two diagonal lines to intersect. If you colour the grid as a chessboard, the two diagonals have the same colour. The points on the knight-move line alternate colour, so the two diagonal lines must intersect the knight-move line in its first and third point. From then on it was trial and error.

• According to my book your answer is correct. But I'm lost at the part where you mentioned about the pentagram. If possible can you please add a drawing to better explain?. In your drawing I can see four different straight lines, but unlike other answerer yours did not consider that trees must be consecutive, but instead one is separated from the other three for example. In your drawing I can see $4$ lines of $4$ trees and barely identity one additional starting on the tree in the sixth row, seventh column and ending on seventh row, first column?. Nov 28, 2019 at 11:23
• I do strongly believe that your answer would be greatly benefited if you could add some colors overlapping your drawing so I can identify where are the lines. Btw the problem did mentioned about straight lines, but didn't this imply that a line must be continous in other words made by a set of contigous trees?. Nov 28, 2019 at 11:25
• When you mentioned the pentagram, did you intended to say that the 10 intersections occur on the outher points of the star and on each leg?. Is that the only way?. Nov 28, 2019 at 11:30
• When you said Each line cuts through the four others, so has four intersection points. There are 10 intersection points in total because any two lines intersect and there are 10 ways to choose two of the 5 lines. Can you explain to me this part using a drawing please?. Because I'm stuck there. Nov 28, 2019 at 11:31
• @ChrisSteinbeckBell I have changed the picture to show lines. Things being in a straight line does not imply that they are equidistant, let alone adjacent. Any arrangement of 5 lines without any parallel ones results in 10 intersections, 4 on each line. The 5 lines that form the sides of a pentagram are just one example. The 5 lines of trees in the solution to this puzzle is another. If you label the 5 lines A, B, C, D, E, then there are 10 ways to choose a pair of lines: AB, AC, AD, AE, BC, BD, BE, CD, CE, DE. Each pair have one intersection point. Nov 28, 2019 at 12:21

Consider the mini-arrangement of trees below:

 xxxx
xx
xx
xxxx

This arrangement contains 6 straight lines of 4 trees each - 2 horizontal, 2 diagonal, and 2 vertical. Essentially, this means you only need a total of 12 trees to achieve 5 straight lines of 4 trees each, and you can chop down all the remaining trees. Since we start with 49 trees, subtract 12 trees (needed for arrangement) to get the number of trees you can chop down, 35 (36 is the closest less than this number).

The final arrangement of trees after chopping everything down should look something like this:

 TTTT___
_TT____
_TT____
TTTT___
_______
_______
_______

Wherein _ signifies a cut down tree and T signifies a tree that remains.

• Can you prove this is optimal? For example, if you can find an arrangement of trees in the shape of a rot13(cragntenz) then you can chop down 39 trees. Nov 27, 2019 at 6:48
• @JaapScherphuis Why not just big rot13(Y), when they can be on each other anyway. Nov 27, 2019 at 6:56
• @Avi The answer is $39$ not $36$. The answer from Jaap is correct. Nov 28, 2019 at 11:16
• @ChrisSteinbeckBell Indeed.
– Avi
Nov 28, 2019 at 19:12

I interpreted the problem to mean that there should be 5 rows of 4 consecutive trees remaining; to maximize the number of cut-down trees, we should make the remaining rows overlap as much as possible. If the rows must be of consecutive trees, you can arrange the remaining trees like this: So there are 5 rows of 4 consecutive palm trees; and we have done so by keeping only 13 trees.

So 49-13=36 trees are remaining.

• Your answer is the only one which uses my original sketch however the correct answer is $39$. Although I felt that your explanation was easier to understand than from others. Nov 28, 2019 at 11:13

I would approach it more like:

(or in text:)

 A B C D E F G
H . . . . . .
J . . . . . .
K . . . . . .

Such that the lines are:

A B C D; B C D E; C D E F; D E F G; A H J K

Which gives us a result of:

keeping 10 trees and cutting down 39.

• I'd really wish that you included an actual diagram, as to decipher a pattern from straight lines is not very intuitive. But the most important part for me is the justification why?. Nov 28, 2019 at 11:12