Booth Id:
MATH012
Category:
Mathematics
Year:
2021
Finalist Names:
Su, Ting-Yun (School: Taipei Municipal Jianguo High School)
Abstract:
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 φ(G(m,n)). It is not difficult to see that
φ(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 φ(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 φ(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 φ(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.