Toán 10 thì đào đâu ra bài này nhỉ :-/
e có thể làm như sau.
Trước hết phép nhân mà e nói a gọi tắt là "nhân hàng", còn phép trừ là "trừ cột". cột nào mà toàn số 0 sẽ được gọi là "cột 0"
ý tưởng:
1. đoán là có thể thu được bảng toàn 0 và chứng minh cho điều ta đoán là đúng
(nếu ko cm được thì cm điều ngược lại
) ) [thực tế là có thể]
2. chứng minh rằng có thể biến 1 cột bất kỳ về toàn số 0
3. chứng minh tiếp nếu 1 cột đã toàn về số 0 rồi ta đi biến đổi cột khác về 0 thì cũng ko ảnh huởng gì đến cột 0 trược đó.
bây h thì tiến hành thôi
Giải
Bước 1 : túm một cột bất kỳ. vì mỗi lần trừ chỉ giảm đi 1 đơn vị nên, thực hiện phép trừ cột liên tiếp đến khi xuất hiện ô đầu tiên có giá trị bằng 1.
khi đó có 2 khả năng
1a/ tất cả ô của cột đều là 1 => nhảy luôn xuống bước 3.
1b/ có i ô là với [TEX]1 \leq i <m[/TEX]. những ô còn lại lớn hơn 1 => nhảy xuống bước 2.
Bước 2: cột của ta có i ô bằng 1 và m-i ô lớn hơn 1.
ta thực hiện liên tiếp 2 phép sau
2a/ với các ô bằng 1 nhân hàng chứa nó với 2 -> ô này thành 2
2b/ thực hiện phép trừ cho cột đang xét -> i ô được nhân thành 2 lại trở về 1, còn m-i ô lớn hơn 1 ở đầu bước 2 kia, mỗi ô được giảm đi 1.
Cứ thực hiện liên tục bước 2a + 2b cho đến khi cột về toàn số 1 thì thôi
Bước 3: bây h các ô của cột toàn số 1 nên thực hiện phép trừ cột là được cột 0.
Vậy ta có thể đưa 1 cột bất kỳ về cột 0.
Như thế ta lần lượt đưa các cột khác về 0 là ok ,
nhưng vấn đề là nhỡ ko may khi ta đưa cột khác về 0 thì cái cột 0 vừa nãy nó lại bị phá mất ko còn là cột 0 nữa thì sao
Ta phải chứng minh là cái tình huống oái oăm ấy nó ko thể xảy ra được
Nhận thấy nếu một cột đã về 0 rồi khi ta biến đổi cột khác thì phép nhân hàng chả xi nhê gì với cột 0 đó cả (2x0=0)
Còn phép trừ chỉ thực hiện trên những cột đang biến đổi nên cũng chả ảnh hưởng gì đến cột 0 kia.
Vậy ta có hai điều sau
I/ luôn biến đổi được 1 cột bất kỳ về 0
II/ khi biến đổi một cột bất kỳ về 0 thì chả ảnh hưởng gì đến những cột 0 đã có.
Vậy túm lại là dù có thể rất vất vả qua nhiều bước, nhưng ta vẫn đưa 1 bảng bất kỳ về bẩng 0 thông qua 2 phép toán trên
|