2 replies to this topic

[DarkBlood]

1) Cho hai tập hợp số nguyên dương phân biêt mà mỗi số đều nhỏ hơn $n.$ Chứng minh rằng nếu tổng số phần tử của hai tập hợp không nhỏ hơn $n$ thì có thể chọn được trong mỗi tập hợp một phần tử sao cho tổng của chúng bằng $n.$

2) Có $20$ người quyết định đi bơi thuyền bằng $10$ chiếc thuyền đôi. Biết rằng nếu hai người $A$ và $B$ mà không quen nhau thì tổng số những người quen của $A$ và những người quen của $B$ không nhỏ hơn $19.$ Chứng minh rằng có thể phân công họ vào các thuyền đôi sao cho mỗi thuyền đều là hai người quen nhau.

3) Cho các số tự nhiên từ $1$ đền $2009.$ Hỏi có thể chọn ra nhiều nhất là bao nhiêu số sao cho tổng của hai số bất kì trong chúng không chia hết cho hiệu của nó?

Edited by DarkBlood, 04-06-2014 - 00:39.

[SuperReshiram]

1) Cho hai tập hợp số nguyên dương phân biêt mà mỗi số đều nhỏ hơn $n.$ Chứng minh rằng nếu tổng số phần tử của hai tập hợp không nhỏ hơn $n$ thì có thể chọn được trong mỗi tập hợp một phần tử sao cho tổng của chúng bằng $n.$

2) Có $20$ người quyết định đi bơi thuyền bằng $10$ chiếc thuyền đôi. Biết rằng nếu hai người $A$ và $B$ mà không quen nhau thì tổng số những người quen của $A$ và những người quen của $B$ không nhỏ hơn $19.$ Chứng minh rằng có thể phân công họ vào các thuyền đôi sao cho mỗi thuyền đều là hai người quen nhau.

3) Cho các số tự nhiên từ $1$ đền $2009.$ Hỏi có thể chọn ra nhiều nhất là bao nhiêu số sao cho tổng của hai số bất kì trong chúng không chia hết cho hiệu của nó?

Mấy bài này ở trong cuốn "Tài liệu chuyên Toán THCS - Toán 7 tập 1 - Đại số", phần Đi-rích-lê bạn ạ!

1) Giả sử hai tập hợp số nguyên dương đã cho là $A=\left \{ a_1;a_2;...;a_m \right \} ;B=\left \{b_1;b_2;...;b_k \right \}$

     Xét tập $C=\left \{ n-b_1;n-b_2;...;n-b_k \right \}$. Có n-1 số nguyên dương khác nhau nhỏ hơn n, các phần tử của A và C đều nhỏ hơn n và tổng số phần tử của A và C ko nhỏ hơn n. Theo Đi-rích-lê tồn tại ít nhất hai phần tử bằng nhau, mỗi phần tử thuộc một tập A và C tức là tồn tại $a_p\in A, n-b_p\in C$ và $a_p=n-b_p\Rightarrow a_p+b_p=n$

Từ đây có đpcm.

Edited by SuperReshiram, 04-06-2014 - 16:54.

[SuperReshiram]

1) Cho hai tập hợp số nguyên dương phân biêt mà mỗi số đều nhỏ hơn $n.$ Chứng minh rằng nếu tổng số phần tử của hai tập hợp không nhỏ hơn $n$ thì có thể chọn được trong mỗi tập hợp một phần tử sao cho tổng của chúng bằng $n.$

2) Có $20$ người quyết định đi bơi thuyền bằng $10$ chiếc thuyền đôi. Biết rằng nếu hai người $A$ và $B$ mà không quen nhau thì tổng số những người quen của $A$ và những người quen của $B$ không nhỏ hơn $19.$ Chứng minh rằng có thể phân công họ vào các thuyền đôi sao cho mỗi thuyền đều là hai người quen nhau.

3) Cho các số tự nhiên từ $1$ đền $2009.$ Hỏi có thể chọn ra nhiều nhất là bao nhiêu số sao cho tổng của hai số bất kì trong chúng không chia hết cho hiệu của nó?

2) Dễ thấy luôn tồn tại một số cặp quen nhau. Xếp mỗi cặp quen nhau đó vào một thuyền đôi. Gọi k là số thuyền lớn nhất mà ta có thể xếp được những cặp quen nhau. Giả sử $k\leq 9$, kí hiệu M là tập hợp những người chưa dc xếp vào thuyền nào. Chọn hai người A và B của tập M thì tổng số người quen của A và B ko bé hơn 19 và những người quen A hoặc B đã dc xếp lên thuyền rồi. Như vậy có 19 người quen A hoặc B đã dc xếp vào nhiều nhất 9 thuyền nên theo Đi-rich-lê có ít nhất 1 thuyền chở 2 người quen cả A và B. Ta s/x lại như sau: k-1 thuyền đầu tiên vẫn giữ nguyên, thuyền thứ k chở $A_k$ và B, thuyền thứ k+1 chở A và $B_k$. Cứ theo cách s/x này thì tiếp tục cho đến hết 10 thuyền, ta có cách s/x thỏa đ/k đề bài.

P/s: Mình bỏ một số câu lập luận cho nhanh, có gì bạn tự suy nghĩ nhé!