« Vrati se
Consider a m\times n rectangular board consisting of mn unit squares. Two of its unit squares are called adjacent if they have a common edge, and a path is a sequence of unit squares in which any two consecutive squares are adjacent. Two parths are called non-intersecting if they don't share any common squares.

Each unit square of the rectangular board can be colored black or white. We speak of a coloring of the board if all its mn unit squares are colored.

Let N be the number of colorings of the board such that there exists at least one black path from the left edge of the board to its right edge. Let M be the number of colorings of the board for which there exist at least two non-intersecting black paths from the left edge of the board to its right edge.

Prove that N^{2}\geq M\cdot 2^{mn}.

Slični zadaci

#NaslovOznakeRj.KvalitetaTežina
1862IMO Shortlist 1993 problem C50
2182IMO Shortlist 2005 problem C110
2183IMO Shortlist 2005 problem C28
2186IMO Shortlist 2005 problem C55
2244IMO Shortlist 2007 problem C43
2299IMO Shortlist 2009 problem C30