a) Giả sử tồn tại cách xếp sỏi thỏa yêu cầu, khi đó để được 8 điểm thì trên tất cả các cột, các đường chéo, các hàng đều phải có sỏi. VÌ không có ô ở trung tâm nên mỗi đường chéo chỉ có thể có 1 viên sỏi và chúng bắt buộc phải nằm trên 1 hàng, khi đó, hàng đó phải chứa 3 ô. Dễ thấy không còn bất kì cách xếp sỏi nào thỏa ycđb để đưa số sỏi trên các hàng, trên các cột, trên các đường chéo về số lẻ nên không tồn tại cách xếp sỏi thỏa ycđb.
b)Số cách xếp các viên sỏi vào bảng $3 \times 3$ mà không để ý tới điểm:
$ \sum_{i=0}^9 C_{9}^{i}=2^9$ cách. tới đây thì dễ thấy số cách xếp sỏi không để ý tới điểm chính là số tập con của tập A={1,2,...,9}. Vậy nên ta sẽ chuyển bài toán về chứng minh số tập con có một số lẻ phần tử của $A$ bằng số tập con có số chẵn phần tử của $A$ và đều bằng $2^8$. Ta sẽ chứng minh tổng quát với tập T có n phần tử. Trước hết, ta sẽ đếm số tập con có chẵn phần tử của của T. Số các tập này là: $\sum C_{n}^{2k}$. Để có một tập con có chẵn phần tử của T, trước hết ta chọn ra $n-1$ phần tử cố định và chọn tiếp 1 tập con bất kì của $n-1$ phần tử. Nếu tập con đã chọn ra có số chẵn phần tử tử thì ta đã có một tạp con có chẵn phần tử của T, nếu tập con đã chọn là lẻ thì bổ sung còn lại của T vào tập con đó. Khi đó ta cũng có 1 tập con có chẵn phần tử của T. Vì vậy số tập con có chẵn phần tử của T là $2^{n-1}$ phần tử và vì số tập con của T là $2^n$ nên số tập con có số lẻ phần tử cũng bằng $2^n-2^{n-1}=2^{n-1}$ phần tử. Vậy ta có đpcm.
Chủ đề bị khóa
