Question

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

Answer 1

最少要取走11個棋子，才可能使得余下的棋子沒有五子連珠

最少要取出11個棋子，才可能滿足要求。其原因如下：
如果一個方格在第i行第j列，則記這個方格為(i，j)。
第一步證明若任取10個棋子，則余下的棋子必有一個五子連珠，即五個棋子在一條直線（橫、豎、斜方向）上依次相連。用反證法。假設(shè)可取出10個棋子，使余下的棋子沒有一個五子連珠。如圖1，在每一行的前五格中必須各取出一個棋子，后三列的前五格中也必須各取出一個棋子。這樣，10個被取出的棋子不會分布在右下角的陰影部分。同理，由對稱性，也不會分布在其他角上的陰影部分。第1、2行必在每行取出一個，且只能分布在(1，4)、(1，5)、(2，4)、(2，5)這些方格。同理(6，4)、(6，5)、(7，4)、(7，5)這些方格上至少要取出2個棋子。在第1、2、3列，每列至少要取出一個棋子，分布在(3，1)、(3，2)、(3，3)、(4，1)、(4，2)、(4，3)、(5，1)、(5，2)、(5，3)所在區(qū)域，同理(3，6)、(3，7)、(3，8)、(4，6)、(4，7)、(4，8)、(5，6)、(5，7)、(5，8)所在區(qū)域內(nèi)至少取出3個棋子。這樣，在這些區(qū)域內(nèi)至少已取出了10個棋子。因此，在中心陰影區(qū)域內(nèi)不能取出棋子。由于①、②、③、④這4個棋子至多被取出2個，從而，從斜的方向看必有五子連珠了。矛盾。
                    
圖1                                                                                    圖2
第二步構(gòu)造一種取法，共取走11個棋子，余下的棋子沒有五子連珠。如圖2，只要取出有標號位置的棋子，則余下的棋子不可能五子連珠。
綜上所述，最少要取走11個棋子，才可能使得余下的棋子沒有五子連珠。