Phương Pháp Qui Nạp

quockhanh · 14-01-2008, 11:55 PM

Chứng minh rằng từ n+1 số bất kỳ trong 2n số nguyên dương đầu tiên luôn có thể tìm được hai số là bội của nhau

nbkschool · 15-01-2008, 12:54 AM

Cái này em ko rành lắm,làm thử thôi.:burnjossstick:
Với n=1 và n=2 thì hiển nhiên đúng.Giả sử đúng tới n=p,ta c/m nó đúng với n=p+1.
Nếu trong p+2 số chọn ra có p+1 số nằm trong khoảng từ 1 tới 2p thì ko còn gì để bàn (vì theo giả thuyết thì trong 2p số bất kì chọn ra p+1 số có 2 số là bội của nhau).Nếu giả sử có p số trong khoảng p+1 và 2 số còn lại là 2p+1 và 2p+2 thì ta có 2p+2 chẵn.Xét p số bất kì từ 1 tới 2p thì có 2 khả năng:
-Nếu có ít nhất 1 số chẵn thì 2p+2 sẽ là bội của số đó.
-Nếu toàn là số lẻ thì có dính số 1 trong đó .:burnjossstick:
Vậy giả thuyết qui nạp đã được chứng minh =) đpcm.

**psquang_pbc** · 15-01-2008, 12:50 PM

Đặt $i=2^{s_i}.t_i $ với $i=\overline{1,2n} $

Ta có chọn ra $n+1 $ số mà chỉ có $n $ số lẻ trong đoạn từ 1 đến $2n $. Do đó tồn tại 2 số $m, n $ sao cho $t_m=t_n $. $(m,n) $ là 2 số cần tìm.

dong1919 · 15-01-2008, 01:05 PM

Thực chất chỉ cần xét n cặp (1;2) ,(2;4), (3,6),...(n,2n)
n+1 số bất kì phải chứa ít nhất 1 trong n cặp trên

**psquang_pbc** · 15-01-2008, 01:14 PM

Đông xem lại nhé.

dong1919 · 15-01-2008, 08:03 PM

Hix chia nhầm
n=2k thì chia thành
$ (1,2,4,8,...,2n) ; (3,6,...2^k.3),(5,10,...)... ,(2i+1,2(2i+1)) $ với 2i+1 < n
có k số ko nằm trong các nhóm này
=> tồn tại k+1 số nằm trong các nhóm này
Mà số nhóm này < k => tồn tại 2 số cùng 1 nhóm
=> 2 số đó chia hết cho nhau
tương tự với n lẻ
còn bài quang cũng nên sửa lại đi

**psquang_pbc** · 15-01-2008, 08:25 PM

uh, quên mất, sửa rồi đó. Mà hình như là cách chia 2 lần khác nhỉ

dong1919 · 15-01-2008, 08:35 PM

chia nhầm mà

14-01-2008, 11:55 PM	#1
quockhanh +Thành Viên+ Tham gia ngày: Dec 2007 Bài gởi: 20 Thanks: 0 Thanked 5 Times in 3 Posts	Phương Pháp Qui Nạp Chứng minh rằng từ n+1 số bất kỳ trong 2n số nguyên dương đầu tiên luôn có thể tìm được hai số là bội của nhau

15-01-2008, 12:50 PM	#3
psquang_pbc +Thành Viên Danh Dự+ Tham gia ngày: Nov 2007 Bài gởi: 747 Thanks: 9 Thanked 111 Times in 72 Posts	Đặt $i=2^{s_i}.t_i $ với $i=\overline{1,2n} $ Ta có chọn ra $n+1 $ số mà chỉ có $n $ số lẻ trong đoạn từ 1 đến $2n $. Do đó tồn tại 2 số $m, n $ sao cho $t_m=t_n $. $(m,n) $ là 2 số cần tìm. __________________ [Only registered and activated users can see links. ] No pain, no gain! thay đổi nội dung bởi: psquang_pbc, 15-01-2008 lúc 08:11 PM

15-01-2008, 01:14 PM	#5
psquang_pbc +Thành Viên Danh Dự+ Tham gia ngày: Nov 2007 Bài gởi: 747 Thanks: 9 Thanked 111 Times in 72 Posts	Đông xem lại nhé. __________________ [Only registered and activated users can see links. ] No pain, no gain!

15-01-2008, 08:25 PM	#7
psquang_pbc +Thành Viên Danh Dự+ Tham gia ngày: Nov 2007 Bài gởi: 747 Thanks: 9 Thanked 111 Times in 72 Posts	uh, quên mất, sửa rồi đó. Mà hình như là cách chia 2 lần khác nhỉ __________________ [Only registered and activated users can see links. ] No pain, no gain!

15-01-2008, 12:54 AM	#2
nbkschool +Thành Viên+ Tham gia ngày: Dec 2007 Đến từ: SMU Residence @Prinsep Hostel, 83 Prinsep Street, Singapore Bài gởi: 400 Thanks: 72 Thanked 223 Times in 106 Posts	Cái này em ko rành lắm,làm thử thôi.:burnjossstick: Với n=1 và n=2 thì hiển nhiên đúng.Giả sử đúng tới n=p,ta c/m nó đúng với n=p+1. Nếu trong p+2 số chọn ra có p+1 số nằm trong khoảng từ 1 tới 2p thì ko còn gì để bàn (vì theo giả thuyết thì trong 2p số bất kì chọn ra p+1 số có 2 số là bội của nhau).Nếu giả sử có p số trong khoảng p+1 và 2 số còn lại là 2p+1 và 2p+2 thì ta có 2p+2 chẵn.Xét p số bất kì từ 1 tới 2p thì có 2 khả năng: -Nếu có ít nhất 1 số chẵn thì 2p+2 sẽ là bội của số đó. -Nếu toàn là số lẻ thì có dính số 1 trong đó .:burnjossstick: Vậy giả thuyết qui nạp đã được chứng minh =) đpcm.

15-01-2008, 01:05 PM	#4
dong1919 Sư tổ Kim Dung-CÁI BANG Tham gia ngày: Nov 2007 Đến từ: A1K35PBC-Nghệ An Bài gởi: 291 Thanks: 0 Thanked 33 Times in 23 Posts	Thực chất chỉ cần xét n cặp (1;2) ,(2;4), (3,6),...(n,2n) n+1 số bất kì phải chứa ít nhất 1 trong n cặp trên

15-01-2008, 08:03 PM	#6
dong1919 Sư tổ Kim Dung-CÁI BANG Tham gia ngày: Nov 2007 Đến từ: A1K35PBC-Nghệ An Bài gởi: 291 Thanks: 0 Thanked 33 Times in 23 Posts	Hix chia nhầm n=2k thì chia thành $ (1,2,4,8,...,2n) ; (3,6,...2^k.3),(5,10,...)... ,(2i+1,2(2i+1)) $ với 2i+1 < n có k số ko nằm trong các nhóm này => tồn tại k+1 số nằm trong các nhóm này Mà số nhóm này < k => tồn tại 2 số cùng 1 nhóm => 2 số đó chia hết cho nhau tương tự với n lẻ còn bài quang cũng nên sửa lại đi

15-01-2008, 08:35 PM	#8
dong1919 Sư tổ Kim Dung-CÁI BANG Tham gia ngày: Nov 2007 Đến từ: A1K35PBC-Nghệ An Bài gởi: 291 Thanks: 0 Thanked 33 Times in 23 Posts	chia nhầm mà