Đã gửi bởi
Bài 4:
câu a.
Nếu cả $m$ và $n$ đều chia hết cho $3$ thì hiển nhiên là ta có nhiều nhất $mn$ số 1.
Giả sử có $m$ hàng và $n$ cột.
Ta có một vài nhận xét sau:
1) Nếu một trong 2 số chia hết cho 3 giả sử là $m$ thì bảng cần ít nhất là $n$ số khác 1 để thỏa mãn
Trường hợp này có thể dễ dàng đưa ra cấu hình thỏa mãn gồm 1 bảng toàn số 1 và 1 cột $m$ số khác 1 (số này là 0 hoặc 2 phụ thuộc vào số dư $n$ chia cho $3$)
2) Nếu 2 số cùng chia cho 3 có chung số dư khác 0. Giả sử $n \ge m$ thì rõ ràng với mỗi cột gồm $m$ ô mà $m$ không chia hết cho $3$ nên phải có ít nhất 1 ô khác 1. Vậy có ít nhất $n$ ô khác 1.
Đưa ra cấu hình thỏa mãn bằng cách chia hình chữ nhật này thành một hình $m$x$m$ và $(n-m)$x$m$. Ta điền cả bảng bằng số 1 ngoại trừ hàng cuối cùng và đường chéo của hình $m$x$m$. Như vậy sẽ có $n$ ô trống, dựa vào số dư của $m,n$ cho $3$ có thể điền vào các ô này thỏa mãn đề bài.
Vậy có trường hợp này có nhiều nhất $(m-1)n$ với $n \ge m$
Thực ra thì khi xây dựng cấu hình thỏa mãn bài toán, một cách tự nhiên ta sẽ nghĩ đến là điền tất cả các số đều là 1 trừ hàng cuối cùng và cột cuối cùng, sau đó tìm số thích hợp điền vào các ô này cho thỏa mãn. Ở trường hợp 1 thì dễ dàng tìm được kết quả, trường hợp 2 để tối ưu ta phải xây dựng một hình vuông $m$x$m$ để đưa về trường hợp 1. Tuy nhiên ta làm đc như vậy vì khi $m$ và $n$ cùng chia $3$ có chung số dư thì các số cần điền ở cuối hàng và cuối cột là như nhau, ta có thể dùng chung bằng cách ghép thành đường chéo hình vuông.
3) Trường hợp $m$ và $n$ chia cho $3$ khác số dư.
Như mình nói ở trên thì sự "cần" để thỏa mãn đề bài giữa hàng và cột là khác nhau nên cần có đến $n+m-1$ ô để thỏa mãn. Tạm thời chưa biết giải thích thế nào cho hợp lí.
Đưa ra cấu hình thỏa mãn thì giả sử $m$ chia $3$ dư $2$ thì cho một cột gồm $m$ số $0$ đưa về bài toán với $n-1$ và $m$ lại đưa về trường hợp trên. Làm ngược lại nếu $n$ chia $3$ dư $2$.
Vế b có lẽ là áp dụng vế a, hoặc cũng có thể dùng thủ thuật chia thành khối lập phương như mình đã dùng chia hình vuông ở trên.
Bài 6:
Trước tiên là quy nạp theo $n$ để chứng minh với $k=1$.
Chú ý là tất cả các phần tử của $B_0^{n+1}$ thu được bằng cách lấy một phần tử của $B_{0}^n$ nhân 2 hoặc lấy một phần tử của $B_{1}^n$ nhân 2 cộng 1. Ngược lại một phần tử của $B_1^{n+1}$ thi được bằng cách lấy phần tử của $B_1^n$ nhân 2 hoặc lấy một phần tử của $B_0^n$ nhân 2 cộng 1. Điều này chứng tỏ tổng các phần tử của $B_0^{n+1}$ và $B_1^{n+1}$ là bằng nhau.
Như vậy với $k=1$ thì bài toán đúng với mọi $n$. Giờ lại chứng minh quy nạp theo $k$.
Đầu tiên đặt $A_0^n$ và $A_1^n$ là tập các chuỗi tận cùng bằng $0$ và $1$ trong $B_0^n$ còn $C_0^n$ và $C_1^n$ là tập các chuỗi tận cùng bằng $0$ và $1$ trong $B_1^n$.
Giả sử bài toán đúng đến $n$ với mọi và với mọi số $k$ bé hơn $t$.
Ta có
$$ \sum_{a \in B_0^{n+1}} (v(a))^t = \sum_{a \in A_0^{n+1}} (v(a))^t+\sum_{a \in A_1^{n+1}} (v(a))^t = \sum_{a \in B_0^n}2^t(v(a))^t+\sum_{a \in B_1^n} (2v(a)+1)^t$$
Tương tự thì:
$$ \sum_{a \in B_1^{n+1}} (v(a))^t = \sum_{a \in C_0^{n+1}} (v(a))^t+\sum_{a \in C_1^{n+1}} (v(a))^t = \sum_{a \in B_1^n}2^t(v(a))^t+\sum_{a \in B_0^n} (2v(a)+1)^t$$
Ta xét đa thức $P(x)= (2x+1)^t-2^t.x^t$ thì $P(x)$ là một đa thức bậc $t-1$.
Dễ thấy là ta đpcm tương đương với:
$$ \sum_{a \in B_0^{n}} P(v(a)) = \sum_{a \in B_1^{n}} P(v(a))$$
Theo giả thiết quy nạp thì $ \sum_{a \in B_0^{n}} (v(a))^i = \sum_{a \in B_1^{n}} (v(a))^i$ với mọi $i \le t-1$ nên đẳng thức trên là hiển nhiên với $degP \le t-1$.
