Turning Grids into Forests

Overview

This research aims to find strategies to solve the following problem: the minimum number of ant-sucking machines which are needed to guarantee the capture of all ants on an m by n grid graph G(m,n). This problem is equivalent to finding a set of minimum number of vertices which are needed on G(m,n) so that the perimeter of each cell contains at least one vertex of the set, or how many vertices must be deleted on such a grid so that the grid turns into a forest. The number of vertices mentioned above is denoted by f(G(m,n)). It is not difficult to see that f(G(m,n)) = [ ((m-1)(n-1)+1)/3 ]=L, where [ ] is the ceiling function. By using constructive methods, we first obtain an upper bound for f(G(m,n)) which is L+1 and discover that for all m, n = 6, (a) if (m,n)=(0,2), (0,5), (2,3), (3,2), (2,0), (5,0) (mod 6), then f(G(m,n))=L+1, and (b) if m=1 (mod 3), n=1 (mod 3) or (m,n)=(3,3), (5,5) (mod 6), then f(G(m,n))=L, Comparing to the known results on this problem, we are able to obtain all of them by using our method. Moreover, we can determine the exact value of two of the ten cases which remain unsolved.

Competition history

• ISEF 2021 Mathematics · Entry MATH012

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.