Đến nội dung


Hình ảnh

Chứng minh chia hết


  • Please log in to reply
Chủ đề này có 2 trả lời

#1 cvp

cvp

    Sĩ quan

  • Thành viên
  • 400 Bài viết
  • 0 points
  • Giới tính:Nam
  • Đến từ:Sky Math
  • Sở thích:Sky maths

Đã gửi 18-10-2011 - 21:09

chứng minh rằng trong $12$ số nguyên tố phân biệt luôn chọn ra được $6$ số ,gọi là $a_{1};a_{2};a_{3}...;a_{6}$ sao cho :
$(a_{1}-a_{2})(a_{3}-a_{4})(a_{5}+a_{6})\vdots 1800$

Hình đã gửi


#2 hxthanh

hxthanh

  • Thành viên
  • 3141 Bài viết
  • -1 points
  • Giới tính:Nam

Đã gửi 20-10-2011 - 02:52

Nếu là $11$ số nguyên tố lớn hơn $3$ thì bài toán sẽ đơn giản hơn
-------------------------------------------------------------------------------------
Chỉ có duy nhất một số nguyên tố chẵn đó là số $2$. số nguyên tố lẻ nhỏ nhất là $3$
Ta sẽ chứng minh: "Trong $11$ số nguyên tố lẻ phân biệt ($>3$), ta luôn chọn ra được $6$ số $p_1,p_2,...,p_6$ sao cho:
$(p_1-p_2)(p_3-p4)(p_5+p_6)\;\vdots\;1800\;\;\;\;(*)$
Sở dĩ thêm chữ "phân biệt" là bởi vì nếu có 2 số giống nhau thì có hiệu bằng $0$, chia hết cho bao nhiêu mà chẳng được :)
Một số nguyên tố lẻ (>3) bất kỳ đều biểu diễn được dưới dạng $6k+1$ (nhóm 1) hoặc $6k-1$ (nhóm 2)
Vì sao lại thế?
(Một số nguyên khi chia $6$ chỉ có các số dư là $\{0,1,2,3,4,5\}$ nếu dư ${0,2,4}$ thì là số chẵn, còn dư $3$ thì là số chia hết cho $3$)
=============== Dài dòng quá nhỉ? ===============
Chọn ra $11$ số nguyên tố lẻ thì có các khả năng sau xảy ra:
  • $6$ số ở nhóm 1 + $5$ số ở nhóm 2
  • $7$ số ở nhóm 1 + $4$ số ở nhóm 2
  • $\ge 8$ số ở nhóm 1 + $\le 3$ số ở nhóm 2
Vì vai trò nhóm 1 hay nhóm 2 không khác gì nhau, nên chỉ cần xét từng đó khả năng là đủ!

Với 3 yếu tố quan trọng sau:
Hiệu 2 số bất kỳ trong cùng 1 nhóm bao giờ cũng chia hết cho $6$
Tổng 1 số ở nhóm này với 1 số ở nhóm kia bao giờ cũng chia hết cho $6$
Tổng hoặc hiệu của 2 số lẻ là số chia hết cho $2$ :)
  • $6$ số ở nhóm 1 + $5$ số ở nhóm 2
- Khi chia 1 số cho $5$ thì có nhiều nhất $5$ loại số dư {0,1,2,3,4}.

- Với $6$ số phân biệt ở nhóm 1 thì luôn tìm được ít nhất $2$ số có cùng số dư khi chia cho $5$ (Dirichlet). Giả sử là $p_1,p_2$ như vậy hiệu $(p_1-p_2)$ chia hết cho $5$ (và chia hết cho $6$)
$\Rightarrow (p_1-p_2)\;\vdots\;30$

- Còn lại $4$ số ở nhóm 1 + $5$ số ở nhóm 2

- Trong $5$ số ở nhóm 2 hoặc $4$ số còn lại bên nhóm 1, mà cũng tìm được $2$ số có cùng số dư khi chia cho $5$ thì sẽ có một hiệu nữa chia hết cho $30$. Cùng với tổng 2 số bất kỳ chia hết cho $2$ nữa là thoả mãn (*).

- Nếu không, sẽ tìm được $2$ số bên nhóm 1 với $2$ số bên nhóm 2 có cùng dư khi chia cho $5$.Giả sử là $p_3,p_4$ và $p_5,p_6$. Như vậy hiệu $(p_3-p_4)$ chia hết cho $5$ (và chia hết cho $2$)
$\Rightarrow (p_3-p_4)\;\vdots\;10$. Cùng với tổng $(p_5+p_6)$ chia hết cho $6$ là thoả mãn (*).
  • $7$ số ở nhóm 1 + $4$ số ở nhóm 2
- Sau khi lấy ra 1 cặp có hiệu chia hết cho $30$ ở nhóm 1, thì còn lại $5$ số ở nhóm 1 + $4$ số ở nhóm 2

- Lập luận tương tự trường hợp trên, ta tìm được các số thoả mãn (*)
  • $\ge 8$ số ở nhóm 1 + $\le 4$ số ở nhóm 2
- Trường hợp này đơn giản hơn vì tìm được 2 cặp có hiệu chia hết cho $30$ ở nhóm 1. Cùng với tổng 2 số bất kỳ chia hết cho $2$ nữa là thoả yêu cầu (*).
------------------------------------------------------------------

Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 20-10-2011 - 10:49


#3 Zaraki

Zaraki

    Hiệp sỹ biển khơi Jinbei

  • Điều hành viên OLYMPIC
  • 3306 Bài viết
  • 0 points
  • Giới tính:Nam
  • Đến từ:Đảo mộng mơ.
  • Sở thích:Geometry, Number Theory, Combinatorics

Đã gửi 21-10-2011 - 19:53

Xin giải ngắn gọn hơn.

Vì ba số nguyên tố đầu tiên là $2,3,5$, do đó trong $12$ số nguyên tố phân biệt đã cho luôn có ít nhất $9$ số lớn hơn $5$.
Vì là số nguyên tố lớn hơn 5 nên

+ $9$ số trên khi chia cho $3$ dư $1$ hoặc $2$. Theo nguyên lí Dirichlet phải tồn tại ít nhất $5$ số đồng dư với nhau $\mod 3$. Năm số này lại không chia hết cho $5$ vì thế trong năm số ấy lại có ít nhất hai số mà ta có thể giả sử là $a_1,a_2$ sao cho $a_1 \equiv a_2 \pmod{5}$. Ngoài ra dĩ nhiên ta có $a_1 \equiv a_2 \pmod{3}$. Từ đó $a_1-a_2 \vdots 15$. Mặt khác $a_1$ và $a_2$ cùng lẻ nên $a_1-a_2 \vdots 2$. Do đó $a_1-a_2 \vdots 30$.

+ Xét $7$ số còn lại : Theo nguyên lí Dirichlet tồn tại $4$ số đồng dư với nhau theo $\mod 3$. Đem $4$ số này chia cho $5$. Có hai khả năng xảy ra:

a) Nếu có hai số chẳng hạn (mà ta sẽ gọi là $a_3,a_4$) mà $a_3 \equiv a_4 \pmod{5}$. Từ đó $a_3-a_4 \vdots 5$. Rõ ràng $a_3-a_4 \vdots 3$ và $a_3-a_4 \vdots 2$. Mà $(5,2,3)=1$ nên $a_3-a_4 \vdots 30$. Lấy hai số $a_5,a_6$ bất kì (ngoài $a_1,a_2,a_3,a_4$ đã chọn) thì do $a_5,a_6$ lẻ nên $a_5+a_6 \vdots 2$. Từ đó suy ra:
$$\left(a_1-a_2 \right) \left(a_3-a_4 \right) \left(a_5-a_6 \right) \ \vdots 30.30.2=1800$$

b) Nếu $4$ số này khi chia cho $5$ có các số dư khác nhau là $1,2,3,4$. Giả sử $a_5 \equiv 1 \pmod{5}, a_6 \equiv 4 \pmod{5}$, thì $a_5+a_6 \equiv 0 \pmod{5}$. Với hai số còn lại $a_3,a_4$ thì rõ ràng $a_3-a_4 \vdots 3$ (theo cách chọn $4$ số như trên). Do $a_5,a_6,a_3,a_4$ lẻ nên $a_5+a_6 \vdots 2$ và $a_3-a_4 \vdots 2$. Từ đó suy ra $a_5+a_6 \vdots 10$ và $a_3-a_4 \vdots 6$. Vậy:
$$\left(a_1-a_2 \right) \left(a_3-a_4 \right) \left(a_5-a_6 \right) \ \vdots 30.10.6=1800$$

Tóm lại luôn tồn tại $a_1,a_2,a_3,...,a_6$ phân biệt sao cho:
$$\left(a_1-a_2 \right) \left(a_3-a_4 \right) \left(a_5-a_6 \right) \ \vdots 1800.$$
"God made the integers, and else is the work of man."




0 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh