��� 膃� 14 �����馹� ���

　n, mを正の整数とする. n×mの長方形の部屋のなかに長さ1の衝立(ついたて)をいくつかおいて迷路を作る. ただし, 衝立の置き方は, この部屋の中に一辺1の正方形n×m個を敷き詰めたときにそれらの一辺と重なるようにするものとする. このとき, 次の条件をみたすために必要な衝立の数を求めよ.

• いくつか衝立を選んで, それらが他の衝立や壁と接していないようにはできない.
• 上記の正方形4個からなる一辺2の正方形をとれば, その内部に少なく とも一つ衝立がある.
• いくつかの衝立によって, 部屋が二つに分けられてしまうことはない.

綽�������膩������������障�����.