Bài 2, Mình cũng nghĩ là cái ô đặt máy bơm không được chính nó tưới, đấy là cái khác của bài này với những bài kiểu tô maù đã có.
a, Ta xét $n\geq 2 $
Với m=4, xét bảng $4\times n $ đánh số thứ tự các cột từ 1 đến n. Ta gọi ô ở hàng i, cột j là (i;j)
Ta đánh dấu các ô (1;4k+1);(1;4k+2);(4;4k+3);(4;4k+4)
Hiển nhiên một máy bơm bất kỳ chỉ tưới được tối đa 1 ô trong các ô đánh dấu, suy ra có ít nhất n máy bơm.
Ta luôn chỉ ra được 1 cách đặt n máy bơm thỏa mãn: ví dụ đặt n máy bơm trên hàng thứ 2.
Đọc nhầm đề thành n hàng m cột, ngồi 3 tiếng
b, Ta chứng minh bằng quy nạp n=5k+2,3,4,5,6 thì có ít nhất 4k+2,3,4,5,6 máy
Gọi f(n) là số máy nhỏ nhất cần cho bảng $3\times n $
Ta có nhận xét: Để tưới nước cho bảng $3\times n $ mà cho phép dùng cả máy bơm ở ngoài bảng nhưng vẫn trong 3 hàng thì mất ít nhất f(n) máy bơm.
Thật vậy, với một máy bơm ở ngoài( gs sau cột thứ n) ta cho tương ứng một máy cùng hàng với nó và ở cột n-1, khi đó máy ở trong tưới hết các ô máy ở ngoài tưới, ta có thể bỏ máy ở ngoài.
Dễ kiểm tra với k=1.
Giả sử mệnh đề đúng với 1,2,...n.
Xét bảng $3\times (n+1) $
Xét 1 cách đặt máy thỏa mãn. Ta đi từ cột đầu tiên đi lại.
Xét cột đầu tiên của bảng, nếu nó có chứa ít nhất 2 máy bơm, ta xét n-1 cột cuối , các máy ở cột đầu không thể tưới đến đây, số máy để tưới hết ít nhất n-1 cột cuối trong bảng $3\times n $ theo nhận xét và giả thiết quy nạp nhỏ nhất là f(n-1), suy ra có ít nhất f(n-1)+2 máy. Tương tự như vậy ta thấy nếu trong a cột đầu mà đã có a+1 máy bơm thì phải dùng nhiều hơn f(n-1)+2 máy. Giả sử trong a cột đầu không bao giờ có đến a+1 máy bơm.
Cột đầu tiên có 0 máy thì suy ra ngay cột cạnh nó có 3 máy, 2 cột có 3 máy, loại.
Cột đầu tiên có đúng 1 máy, dễ thấy chỉ có duy nhất 1 vị trí có thể tưới nước cho nó là ô ngay cạnh, vậy ở đây phải có máy bơm, cột này có đúng 1 máy. Ta tiếp tục đi theo cột với thứ tự tăng dần.
Ta chứng minh nếu cứ trong a cột mà có không đến a máy thì sẽ còn cột phía sau. Ta cũng thấy việc lập luận chỉ phụ thuộc vào ta bắt đầu từ cột nào( tức là đi từ cột đầu có x máy cũng như đi từ cột nào đó có x máy)
Xét cột đầu tiên không có máy bơm nào, giả sử là cột thứ k. Theo giả sử cột trước nó có đúng 1 máy bơm, nghĩa là tưới được đúng 1 ô của nó, suy ra còn 2 ô chưa được tưới và phải có 2 máy bơm ở cột k+1( có 3 máy thì vi phạm)
Xét cột k+2, nếu nó không có máy bơm nào thì phải có cột k+3, xét 2 trường hợp:
+, cột k+3 có 1 máy thì chính vị trí của máy chưa được tưới và ta phải có 1 máy kề máy này ở cột k+4.
+, cột k+3 có 2 máy, ta lại tiếp tục xét như trên.
Suy ra nếu cột k không có máy thì phải có ít nhất 4 máy trong 4 cột tiếp theo
Do đó trong 5 cột liên tiếp ta luôn có ít nhất 4 máy bơm, suy ra $f(n+5) \geq f(n)+4 $
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]