Home > Combinatorics, Olympiad, Problem Solving > Snails in a triangular array

Snails in a triangular array


Suppose we have a triangular array in the shape of an equilateral triangle of side 10, and draw all parallel lines to the edges of the triangle such that 100 small equilateral triangles are formed.
Place a snail in each of the 100 small triangles. It is known that in 10 seconds, each snail moves from his cell to an adjacent one. Prove that after 10 seconds, at least 10 triangle cells are free.

Solution: Color the array in a chessboard style, with black and white, such that any two adjacent cells have different colors. Then, notice that the three corner cells have the same color, without loss of generality, suppose that color is black. Then there are 1+2+...+10=55 black squares and 1+2+...+9=45 white squares. Since the “white” snails will turn “black” in 10 seconds and all the “black” snails will move from their cells after 10 seconds, at least 10 black cells will be free after 10 seconds, and this is because there are not enough white snails initially on the board.

This can be easily generalized to a triangular array with n^2 triangles, and then at least n cells will be free after 10 seconds. This is a nice coloring argument, similar to the domino tilling of the chessboard with two opposite corners removed.

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: