Tổ hợp sơ cấp

Posted: Tháng Tư 7, 2014 in Uncategorized
0

Đây là một bài toán hay được chọn lọc .

Cho bảng p x q các ô vuông với p hàng và q cột . Mỗi ô được đánh một số nguyên dương nào đó sao cho trên bảng không có hai số nào bằng nhau . Cho hai số nguyên dương m,n thỏa mãn m \leq p , n \leq q . Một số trên bảng được gọi là số xấu nếu số được đánh dấu ở ô đó nhỏ hơn ít nhất m số cùng hàng và nhỏ hơn ít nhất n số cùng cột   . Gọi S là tất cả các số xấu trên bảng . Tìm Min S với mọi p,q,m,n .

Chứng minh :

Trước hết ta sắp xếp pq các nguyên dương x_{i} với x_{i} < x_{i+1}

Ở hàng thứ nhất xếp các số x_{1},x_{p+1},......x_{(q-1)p+1}

Ở hàng thứ hai xếp các số x_{2} , x_{p+2} .......x_{(q-1)p+2}

……

Ở hàng thứ p ta xếp các số x_{p},x_{2p},......x_{pq}

Rõ ràng bảng này thỏa mãn S = (p-m)(q-n)

Ta chứng minh đây là giá trị cần tìm .

Trước hết nếu p=m hoặc q=n thì bài toán hiển nhiên đúng nên ở đây ta xét cho p < m và n < q

Ý tưởng chính ở đây là quy nạp theo số p +q

Nếu p+q=2 thì hiển nhiên p=q=1 và bài toán đang xét trở nên hiển nhiên

Tất nhiên ta có thể dễ dàng kiểm tra một số trường hợp đầu tiên

Giả sử khẳng định đúng với p+q=k ta chứng minh đúng với p+q=k+1

Định nghĩa :

Một ô được gọi là xấu theo hàng nếu số được đánh ở ô đó nhỏ hơn ít nhất m số được đánh cùng hàng , tương tự cho ô xấu theo cột là ô nhỏ hơn ít nhất n số cùng cột

Xét hàng thứ i bất kỳ trên bảng này .Ta kiểm tra được nó có q-n ô là xấu theo hàng .

Vậy trên mỗi hàng ,cột bất kỳ thì có q-n ô xấu theo hàng và p-m ô là xấu theo cột .

Nếu mỗi ô xấu theo hàng trùng với một ô xấu theo cột . Rõ ràng ta có

                                                S = (p-m)(q-n)

Vì vậy ta quan tâm đến các trường hợp mà một ô chỉ xấu theo hàng hoặc chỉ xấu theo cột .

Gọi a là số xấu theo hàng hoặc xấu theo cột nhỏ nhất trên bảng này

Không mất tỉnh tổng quát giả sử a nằm ở ô xấu theo hàng ( rõ ràng nó không xấu theo cột )

Xét cột chứa số a trên bảng này

Hiển nhiên ta dễ dàng chứng minh được p-m ô xấu theo cột trong cột chứa số a cũng là các ô xấu của bảng px q

Bỏ đi cột chứa số a ta có bảng p x ( q-1)

Rõ ràng theo giả thiết quy nạp thì p+q-1=k

Nên S \geq (p-m)(q-1-n) + (p-1)=(p-m)(q-n)

Bài toán được cm .

Giờ ta có một bài toán họ hàng với bài toán trên .

Cho n em trên sân trường . Ta gọi khoảng cách giữa hai em A,B là AB . Biết rằng nếu AB = CD khi và chỉ khi (A,B) là hoán vị của (C,D).

Sau khi có hiệu lệnh mỗi em cầm một khẩu súng nước trên tay , bắn vào người đứng gần mình nhất . Sau khi kết thúc người không bị bắn là người thắng .

Tìm tất cả các số nguyên dương n để bảo đảm luôn có ít nhất một em là người thắng với mọi cách xếp trên sân .

Chứng minh

Ta sẽ xét n là số lẻ . Nó chính là đáp số bài toán , trong trường hợp n chẵn sẽ dễ dàng có ví dụ bác bỏ .

Đặt n=2m-1 với m là một số nguyên dương .

Quy nạp theo m . Với m=1 thì khẳng định hiển nhiên đúng .

Giả sử nó đúng với m=k , khi m=k+1 thì n = 2k+1

Chọn ra hai em A,B sao cho AB là khoảng cách ngắn nhất giữa em bất kỳ .

Xét tất cả các em còn lại giả sử là A_{1},.......A_{2k-1}

Theo quy nạp trong số các em này có một em C là thắng

Xét tam giác ABC có AB nhỏ nhất .

Ta có A,B không bắn vào C và C lại thắng ở 2k-1 người kia nên C là thắng .

Bài toán được giải quyết .

Một bài toán khác trong ba bài toán hôm nay tôi muốn nói đến

Cho bảng vuông n^{2} . Mỗi ô trên bảng ta đánh một số -1 hoăc là 1 . Lần lượt gọi a_{k},b_{k} là tích tất cả các ô trên hàng k và cột k .

Tồn tại hay không cách đánh số thỏa \sum_{i=1}^{n}a_{i} + \sum_{i=1}^{n}b_{i}=0

Giải :

Câu trả lời là không tồn tại . Sau đây là chứng minh .

Phản chứng giả sử tồn tại cách đánh như vậy .

Lần lượt trên hàng và cột k gọi x_{k},y_{k} là số các số -1 ở đó

Hiển  nhiên ta có a_{k}=(-1)^{x_{k}},b_{k}=(-1)^{y_{k}}

Ta lại có

                                     \sum_{k=1}^{n} ((-1)^{x_{k}}+(-1)^{y_{k}})=0

Với mọi k thì S_{k}=(-1)^{x_{k}}+(-1)^{y_{k}} \in (0,2,-2)

Gọi A là số các số k làm cho S_{k}=0

Gọi B là số các số k mà S_{k}=2

Gọi C là số các số k mà S_{k}=-2

Khi đó hiển nhiên 2B-2C=0 nên B=C

Và hiển nhiên tổng A+B+C=A+2B phải là số lẻ . (1)

Ta có đánh giá sau , gọi T là số các số -1 trên cả bảng

Khi đó ta có   T = \sum_{k=1}^{n}x_{k}=\sum_{k=1}^{n}y_{k}

Với cách gọi trên ta thấy

A,B,C chính là số các bộ (x_{k},y_{k}) mà gồm , một chẵn một lẻ , hai chẵn , hai lẻ .

Cũng từ đánh giá trên ta có

  I=\sum_{k=1}^{n}(x_{k}+y_{k}) là số chẵn

Nhận thấy I = M+N+P

Trong đó M,N,P lần lượt là các giá trị Q_{k}=x_{k}+y_{k} gồm , một chẵn một lẻ , hai chẵn , hai lẻ.

Rõ ràng ta có M phải là số lẻ theo (1) , và N,P hiển nhiên chẵn

Từ các đó cho ta điều vô lý , ta có điều phải chứng minh .

 

 

Bình luận về bài viết này