By
Paolo Baldan, University of Padova
Roberto Bruni, Universtity of Pisa
In a park there is an area including some rare trees. Such trees are planted very regularly at the points of a grid: each tree is determined by its integer coordinates (x,y) with x ∈ [1,n – 1],y ∈ [1,m – 1], as in the figure below.
One day, the park is invaded by some mutant rabbits whose teeth are so strong that they can easily cut a tree trunk. The park is in danger and a fence should be installed to protect the trees. Unfortunately, the park authorities are facing some financial problems and they cannot afford the expense of a rectangular fence including the full grid.
Only a triangular fence, with base on the x-axis, from (0,0) to (m,0) can be installed. The top vertex of the fence must be one of (x,n) for x ∈ [1,m – 1]. Two possibilities are depicted by dotted lines in the figure
below.
Please, help the park authorities to design properly the fence in a way that the largest number of trees will be protected. Remind that trees on the border of the fence will be necessarily cut in advance.
- Show that, independently of the choice of top vertex (x,n), a triangular fence with no trees on the border will always include the same number, say i, of trees. Also observe that fences where some trees fall on the border will include a number of trees smaller than i.
Hint: It is helpful to relate the area of a generic triangle with the number of trees it includes and the number of trees on its border.
- Give a condition on the coordinates of the upper vertex of the triangle ensuring that no tree will be on the border.
A solution proposed by authors can be found is in the PDF attached. Please try it yourself before reading it! The authors welcome any alternative solution (send them via email).