Cho một bảng ô vuông $n\times n$. Điền mỗi ô vuông của bảng bằng một số nguyên sao cho 2 ô nằm cạnh nhau hơn kém nhau không quá 1 đơn vị. Chứng minh có 1 số xuất hiện ít nhất n lần.
Cho một bảng ô vuông $n\times n$. Điền mỗi ô vuông của bảng bằng một số nguyên sao cho 2 ô nằm cạnh nhau hơn kém nhau không quá 1 đơn vị. Chứng minh có 1 số xuất hiện ít nhất n lần.
►|| The aim of life is self-development. To realize one's nature perfectly - that is what each of us is here for. ™ ♫
Cho một bảng ô vuông $n\times n$. Điền mỗi ô vuông của bảng bằng một số nguyên sao cho 2 ô nằm cạnh nhau hơn kém nhau không quá 1 đơn vị. Chứng minh có 1 số xuất hiện ít nhất n lần.
Đầu tiên có nhận xét sau : Cho một số số được viết liên tiếp nhau sao cho khoảng cách giữa hai số liên tiếp không quá 1 . Trong dãy đó , nếu tồn tại một số nhỏ hơn (hoặc bằng) $k$ và một số lớn hơn (hoặc bằng) $k$ thì sẽ có ít nhất một số trong dãy là $k$ .
Trở lại với bài toán :
Gọi $m$ là số lớn nhất trong $n$ số nhỏ nhất của mỗi hàng .
Ta chứng minh $m$ là số nhỏ nhất .
Thật vậy , nếu mỗi hàng đều có một số lớn hơn hoặc bằng $m$ ta áp dụng nhận xét cho từng hàng (đều có số nhỏ hơn hoặc bằng $m$ là số nhỏ nhất mỗi hàng ) thì mỗi hàng có ít nhất một số là $m$
Xét trường hợp tồn tại một hàng nào đó chỉ có toàn số nhỏ hơn $m$ . Ta lại có hàng chứa số $m$ là hàng gồm toàn số lớn hơn hoặc bằng $m$ . Áp dụng nhận xét cho mỗi cột thì mỗi cột có ít nhất một số là $m$
Từ trên có dpcm
0 thành viên, 1 khách, 0 thành viên ẩn danh