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

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.