Chủ đề này có 2 trả lời

[LNH]

Cho một hình vuông $n \times n$ với $n \geq 4$. Ta viết $n$ dấu cộng vào các ô trên một đường chéo lớn của hình vuông trên, các ô còn lại được diền vào dấu trừ. Ta có thể thay đổi bảng trên bằng cách đổi dấu trong các ô cùng một hàng hoặc một cột. Chứng minh rằng: số dấu cộng trên bảng trên luôn không nhỏ hơn $n$ sau một số hữu hạn lần thay đổi.

[dinhthanhhung]

 

Cho một hình vuông $n \times n$ với $n \geq 4$. Ta viết $n$ dấu cộng vào các ô trên một đường chéo lớn của hình vuông trên, các ô còn lại được diền vào dấu trừ. Ta có thể thay đổi bảng trên bằng cách đổi dấu trong các ô cùng một hàng hoặc một cột. Chứng minh rằng: số dấu cộng trên bảng trên luôn không nhỏ hơn $n$ sau một số hữu hạn lần thay đổi.

 

Lời giải :

 

Gọi x_i là số lần biến đổi ở cột thứ i , y_i là số lần biến đổi ở hàng thứ i .

Do đó số lần biến đổi ở ô cột a , hàng b là x_a+y_b . Nếu giá trị này chẵn thì dấu ban đầu được bảo toàn , nếu lẻ thì dấu ban đầu đổi ngược .

Giờ ta phản chứng một lúc nào đó trên bảng có ít hơn n ô được đánh dấu cộng . Theo nguyên lí Dirichlet tồn tại một cột không có số nào được đánh dấu cộng . KMTQ ta giả sử đó là cột 1 .

Khi đó x_1+y_1 phải lẻ , x_1+y_i (i từ 2->n) phải chẵn . Do đó y_i cùng dấu (i từ 2->n) và tất cả khác dấu y_1.

Ta xét các cột còn lại , theo tính chẵn lẻ thì mỗi cột sẽ có 2 hoặc n-2 ô được đánh dấu cộng (dễ chứng minh) , mà n lớn hơn 3 nên mỗi cột có ít nhất 2 .

Do đó số ô được đánh dấu cộng ít nhất là 2(n-1) lớn hơn n-1 .

Vậy phản chứng sai , có dpcm !

 

P/s : Phần mềm gõ công thức bị lỗi , híc :|

Bài viết đã được chỉnh sửa nội dung bởi dinhthanhhung: 02-03-2014 - 23:49

[phatsp]

Khi đó x_1+y_1 phải lẻ , x_1+y_i (i từ 2->n) phải chẵn . Do đó y_i cùng dấu (i từ 2->n) và tất cả khác dấu y_1.
--->cột 1 không có ô nào được đánh dấu (+) thì x_1+y_i phải lẻ (i=1,2...n) chứ nhỉ