4
$\begingroup$

Consider a finite rectangular grid consisting of unit squares (cells). Some cells are colored black, and the rest are white.

Some definitions:

  • Two black cells are neighbors if they share an edge.
  • Two black cells are connected if they are neighbors or both are connected to a third cell.
  • Some black cells form a connected component if they are pairwise connected and no other black cells are connected to them.

Initially, all black cells form a connected component.

Prove or disprove that the following two statements are equivalent:

A. There is no cycle, i.e. it is impossible to start from a black cell, repeatedly move to a neighbor at least three times and return to the starting cell without stepping on a cell at least twice.

B. For any black cell with two or more neighbors, painting it white would split the remaining black cells into two or more connected components.

As an illustrative example, the following satisfies both A and B. # is black, and . is white.

..#..
#####
..#.#
.##.#
##.##

Background (contains a partial spoiler to the puzzle):

In one problem of a recent local programming contest, statement B was used where statement A was intended, leading to an incorrect jury solution. The counterexample was found after the contest, invalidating the round.

$\endgroup$

1 Answer 1

7
$\begingroup$

The statements are

not equivalent.

Here is a simple

counter example:

    . # . .
    . # # #
    # # # .
    . . # .
 

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.