Problem

Source: Tournament of Towns, Fall 2002, Junior A Level, P7

Tags: ceiling function, combinatorics proposed, combinatorics



A power grid with the shape of a $3\times 3$ lattice with $16$ nodes (vertices of the lattice) joined by wires (along the sides of squares. It may have happened that some of the wires have burned out. In one test technician can choose any two nodes and check if electrical current circulates between them (i.e there is a chain of intact wires joining the chosen nodes) . Technicial knows that current will circulate from any node to another node. What is the least number of tests required to demonstrate this? Previous problem for the grid of $5\times 5$ lattice.