方陣問題3----全國高中數學聯賽題目

這是2007年全國高中數學聯賽加試題的題目。

題目

如圖，在7×8的長方形棋盤的每個小方格的中心點各放一個棋子。如果兩個棋子所在的小方格共邊或共頂點，那麼稱這兩個棋子相連。現從這56個棋子中取出一些，使得棋盤上剩下的棋子，沒有五個在一條直線（橫、豎、斜方向）上依次相連。問最少取出多少個棋子才可能滿足要求？並說明理由。

圖1

解答

我們先保證行與列無五連子，這樣1-7行的前5列，每行就至少都需要有一子；再考慮後三列，其前5行每列需有1子，這就是10子了，如圖2。

圖2

因此最少也要取10子出來，並且此時，如圖3，右下角2x3的區域內沒取過1子。

圖3

由對稱性，假設取10子就能達到目的的話，圖4中的4個區域都無子取出。

圖4

1，2行，前5列必須取的兩子分佈在圖5的區域A中

圖5

6，7行前5列必須取的兩子分佈在區域B中，前3列前5行必須取的3子在C區域中，後三列前5行必須取的3子在D區域中。這就是10個子了.所以，圖5中心部分的6個方格就不應該再取子。現在我們說明，這樣的取法不能保證斜線不存在5連子。

圖6

由於圖5中C區域每列需要各取一個子，且總計只能取3子，所以圖6中1，3的位置只能取一個子，2，4位置也只能取一子。對取1，4的情形，圖7畫的黑色斜線上有5子相連.

圖7

如果取的是1，2，圖8所示的黑斜線上有5連子，其它兩種情況具有對稱性，所以，取10個子達不到要求。

圖8

構造一種取法，共取走11個棋子，餘下的棋子沒有五子連珠。如圖8，只要取出有標號位置的棋子，則餘下的棋子不可能五子連珠。

圖9

綜上所述，最少要取走11個棋子，才可能使得餘下的棋子沒有五子連珠。