Đến nội dung


Chú ý

Nếu các bạn đăng kí thành viên mà không nhận được email kích hoạt thì hãy kiểm tra thùng thư rác (spam). Nếu không biết cách truy cập vào thùng thư rác thì các bạn chịu khó Google hoặc đăng câu hỏi vào mục Hướng dẫn - Trợ giúp để thành viên khác có thể hỗ trợ.


Hình ảnh

Thảo luận về Đề thi và Lời giải của IMO 2016

imo

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

#21 lenhatsinh3

lenhatsinh3

    Hạ sĩ

  • Thành viên
  • 86 Bài viết
  • Giới tính:Nam
  • Đến từ:THPT An Nhơn 2
  • Sở thích:Pokemon, giải toán

Đã gửi 12-07-2016 - 15:59

NGÀY 2

Bài 4. Một tập hợp  các số nguyên dương được gọi là tập hương nếu tập hợp đó có ít nhất 2 phần tử và mỗi phần tử của nó đều có ước nguyên tố chung với ít nhất một trong các phần tử còn lại . Đặt $P(n)=n^{2}+n+1$. Hãy tìm số nguyên dương $b$ nhỏ nhất sao cho tồn tại số không âm $a$  để tập hợp  $\left \{ P(a+1);P(a+2);...;P(a+b) \right \}$ tập hương.

Bài 5. Người ta viết lên bảng phương trình:

$(x-1)(x-2)(x-3)...(x-2016)=(x-1)(x-2)(x-3)...(x-2016)$

với 2016 nhân tử bậc nhất ở mỗi vế. Hãy tìm số nguyên dương $k$ nhỏ nhất để có thể xóa đi $k$ nhân tử trong số 4032 nhân tử nêu trên sao cho mỗi vế còn ít nhất một nhân tử và phương trình thu được không có nghiệm thực.

Bài 6. Trong mặt phẳng, cho $n\geq 2$ đoạn thẳng sao cho 2 đoạn thẳng bất kì cắt nhau tại một điểm nằm trên mỗi đoạn và không có ba đoạn thẳng nào đồng quy.Với mỗi đoạn thẳng thầy Minh chọn một đầu mút của nó rồi đặt lên đó một con ếch sao cho mặt con ếch hướng về đầu mút còn lại. Sau đó thầy vỗ tay $n-1$ lần. Mỗi lần vỗ tay con ếch ngay lập tức nhảy đến giao điểm gần nhất trên đoạn thẳng của nó. Tất cả những con ếch đều không thay đổi  hướng nhảy của mình trong toàn bộ quá trình nhảy. Thầy Minh muốn đặt các con ếch sao cho sau mỗi lần vỗ tay không có hai con nào nhảy đến cùng một điểm.

(a). Chứng minh rằng thầy Minh luôn thực hiện được ý định của mình nếu $n$ là số lẻ.

(b).  Chứng minh rằng thầy Minh không thể thực hiện được ý định của mình nếu nếu $n$ là số chẵn.


Bài viết đã được chỉnh sửa nội dung bởi lenhatsinh3: 12-07-2016 - 16:43

:ukliam2:  :ukliam2:  :ukliam2:  :ukliam2:  :ukliam2:

      :ukliam2:

            :ukliam2:

                  :ukliam2:

             :ukliam2:

        :ukliam2:  

     :ukliam2:  :ukliam2:  :ukliam2:  :ukliam2:  :ukliam2:


#22 Bui Ba Anh

Bui Ba Anh

    Thiếu úy

  • Thành viên
  • 562 Bài viết
  • Giới tính:Nam
  • Sở thích:Mathematics

Đã gửi 12-07-2016 - 16:12

Bài 4: Ta gọi tập thỏa mãn đề bài là tập chuẩn

Giả sử với số $b$ nào đó ta thu được tập chuẩn $X$, ta sẽ tìm giá trị nhỏ nhất của $b$

Với mỗi phần tử trong  $X$, nếu nó có ước nguyên tố chung với phần tử nào đó trong các phần tử còn lại thì ta xếp các ước nguyên tố đó vào tập $P$. Sau quá trình này, nếu có nhiều phần tử trùng nhau trong $P$ thì ta chọn một trong chúng

Ta sẽ xét các trường hợp

*TH1: Nếu trong $P$ tồn tại các số nguyên tố lớn hơn hoặc bằng $11$, gọi $p$ là một số như vậy

Khi đó tồn tại $P(a+m)$ và $P(a+n)$ chia hết cho $p$ ($m>n$)

Suy ra $$p|P(a+m)-P(a+n)$$

$$=>p|(m-n)(m+n+1)$$

-Nếu $p|m-n$, khi đó do $m$ khác $n$ nên $m \geq 12$ hay $b \geq 12$

-Nếu $p|m+n+1$ khi đó do $m$ khác $n$ nên $m \geq 6$ hay $ b\geq 6$

Vậy trong trường hợp này $b \geq 6$

*TH2: Nếu trong $P$ chỉ chứa các số nguyên tố $3,5,7$ (vì các phân tử đều là số lẻ)

Rõ ràng $P$ không chưa $5$ vì $n^2+n+1$ không chia hết cho $5$

Ta có $2$ nhận xét:

1. $n^2+n+1$ chia hết cho $3$ khi và chỉ khi $n=1$ mod 3, cũng suy ra là trong ba số liên tiếp thì chỉ có một số $t$ mà $P(t)$ chia hết cho $3$

2.$n^2+n+1$ chia hết cho $7$ khi và chỉ khi $n=2,4$ mod 7, cũng suy ra là trong ba số liên tiếp thì có nhiều nhất hai số mà $P$ của nó chia hết cho $7$,trong 2 số liên tiếp thì có nhiều nhất một số mà $P$ của nó chia hết cho $7$

Trở lại trường hợp này

-Nếu $X$ có $2$ phần tử, điều này vô lí vì số phần tử chia hết cho $3$ là $0$ hoặc $2$, nếu là $0$ thì hai số đó đều chia hết cho $7$ vô lí theo nhận xét. nếu có $2$ số chia hết cho $3$ cũng vô lí theo nhận xét

-Nếu $X$ có $3$ phần tử, nếu có $0$ phần tử chia hết cho $3$, suy ra tất cả đều chia hết cho $7$ là vô lí theo nx2. Nếu có $2,3$ số chia hết cho $3$ vô lí theo nx1.

-Nếu $X$ có $4$ phần tử, nếu có $0$ phần tử chia hết cho $3$ là vô lí theo nx1, nếu có nhiều hơn $2$ phần tử chia hết cho $3$ thì chỉ có thể là $P(a+1),P(a+4)$, suy ra $P(a+2),P(a+3)$ chia hết cho $7$ vô lí theo nx2

-Nếu có $5$ phần tử: Có $0$ phần tử chia hết cho $3$ là vô lí, nếu có $2$ phần tử chia hết cho $3$, dễ thấy có $2$ phần tử liên tiếp trong $X$ chia hết cho $7$ vô lí theo nx2.

Tóm lại trong trường hợp này $b \geq 6$

Ta sẽ chỉ ra min $b$ là 6

Xét số $n$ thỏa mãn: n=0 mod 3, n=5 mod 11, n=6 mod 7. Số này là tồn tại theo định lí số dư trung hoa

Khi đó $3 \mid P(x+1), P(x+4),19 \mid P(x+2),P(x+6),  7 \mid P(x+3), 7 \mid P(x+5)$.


NgọaLong

#23 the unknown

the unknown

    Thượng sĩ

  • Thành viên
  • 208 Bài viết
  • Giới tính:Nam
  • Đến từ:Nothingness
  • Sở thích:unknown

Đã gửi 12-07-2016 - 16:24

Cho em hỏi là bài 6 có phải của Việt Nam mình ra không vậy?

Không đâu bạn, nghe bảo là do Geoff Smith, người nước Anh đề xuất.


$\texttt{If you don't know where you are going, any road will get you there}$


#24 Hoang Nhat Tuan

Hoang Nhat Tuan

    Hỏa Long

  • Thành viên
  • 974 Bài viết
  • Giới tính:Nam
  • Đến từ:11 Toán, THPT chuyên Võ Nguyên Giáp, Quảng Bình
  • Sở thích:Geometry, Combinatorial

Đã gửi 12-07-2016 - 16:57

Câu 4: Một tập hợp các số nguyên dương được gọi là tập hương nếu tập đó có ít nhất 2 phần tử và mỗi phần tử của nó có ước nguyên tố chung với ít nhất một trong các phần tử còn lại. Đặt $P(n)=n^2+n+1$. Hãy tìm số nguyên dương $b$ nhỏ nhất sao cho tồn tại số nguyên không âm $a$ để cho tập hợp 

$$\{P(a+1),P(a+2),...,P(a+b)\}$$

là một tập hương.

Lời giải:

Xét trường hợp $b\leq 5$, sử dụng thuật toán Euclid với lưu ý rằng $P(n)$ không chia hết cho $2$ ta có:

$$gcd(P(a+1),P(a+2))=1$$

$$gcd(P(a+1),P(a+3))|7$$

$$gcd(P(a+1),P(a+4))|3$$

$$gcd(P(a+1),P(a+5))|19$$

Cụ thể hơn, $gcd(P(a+1),P(a+3))=7$ tương đương với $a+1\equiv 2 (\mod 7)$, $gcd(P(a+1),P(a+4))=3$ tương đương với $a+1\equiv 1 (\mod 3)$, $gcd(P(a+1),P(a+5))=19$ tương đương với $a+1\equiv 7 (\mod 19)$

Do đó các ước nguyên tố chỉ có thể nằm trong tập hợp $\{3,7,19\}$

Xét một mặt phẳng và 5 điểm $A_1,A_2,...,A_5$ tương ứng với 5 giá trị của $P(a+1),P(a+2),...,P(a+5)$, $A_k$ và $A_l$ được nối với nhau bởi 1 đoạn thẳng có độ dài $3,7,19$ tương ứng với ước nguyên tố chung của $P(a+k)$ và $P(a+l)$ ($A_i$ không thể nối với $A_{i+1}$).

Trường hợp $b=5$:

Nếu $A_1$ nối với $A_5$, khi đó $A_2$ nối với $A_4$ và $A_3$ nối với $A_1$ hoặc $A_5$ (vô lý)

Nếu $A_1$ nối với $A_3$ thì $A_2$ nối với $A_4$ (loại) nên $A_2$ nối với $A_5$, khi đó $A_4$ phải nối với $A_1$, $a$ phải thỏa mãn:

$a\equiv 6 (\mod 7); a\equiv 2 (\mod 3); a\equiv 0 (\mod 3)$ vô lý.

Nếu $A_1$ nối với $A_4$ thì $A_2$ nối với $A_5$ cũng vô lý.

Vậy trường hợp này loại.

Tương tự, ta xét các trường hợp $b=2,3,4$ còn lại suy ra $b\geq 6$

Trường hợp $b=6$, sử dụng định lý Thặng dư Trung Hoa cho hệ sau:

$$a+1\equiv 7 (\mod19)$$

$$a+2\equiv 2 (\mod 7)$$

$$a+3\equiv a+6\equiv 1 (\mod 3)$$

$$a+4\equiv 4 (\mod 7)$$

$$a+5\equiv 11 (\mod 19)$$

Từ đó suy ra $b=6$ là giá trị nhỏ nhất cần tìm


Bài viết đã được chỉnh sửa nội dung bởi Hoang Nhat Tuan: 13-07-2016 - 07:16

Ngài có thể trói cơ thể tôi, buộc tay tôi, điều khiển hành động của tôi: ngài mạnh nhất, và xã hội cho ngài thêm quyền lực; nhưng với ý chí của tôi, thưa ngài, ngài không thể làm gì được.

#25 Zaraki

Zaraki

    PQT

  • Phó Quản trị
  • 4259 Bài viết
  • Giới tính:Nam
  • Đến từ:Đảo mộng mơ.
  • Sở thích:Geometry, Number Theory, Combinatorics, Manga

Đã gửi 12-07-2016 - 22:31

Các bạn nào chép lời giải từ AoPS lại thì nhớ ghi nguồn nhé. Mình có thử giải bài 6 và chỉ làm được câu a. Lời giải bên AoPS mình nghĩ là hay, nếu bạn nào muốn thử sức thì mình viết cái gợi ý để được lời giải của mấy bạn bên AoPS.

 

Gợi ý


“A man's dream will never end!” - Marshall D. Teach.

#26 hqdh96

hqdh96

    Lính mới

  • Thành viên mới
  • 1 Bài viết

Đã gửi 13-07-2016 - 04:10

Bài 5: Đẳng thức $(x-1)(x-2)...(x-2016)=(x-1)(x-2)...(x-2016)$ được viết trên bảng với 2016 thừa số ở mỗi vế. Xác định giá trị nhỏ nhất có thể của $k$ để ta có thể xoá $k$ trong số 4032 thừa số trên, với điều kiện là mỗi vế còn lại ít nhất một thừa số, để phương trình nhận được sau phép biến đổi là vô nghiệm.

 

Giải: Ta sẽ chứng minh rằng $k=2016$ là giá trị nhỏ nhất cần tìm.

 

Nếu như ta xoá ít hơn 2016 thừa số, thì đẳng thức nhận được chứa ít nhất 2017 thừa số. Do có 2016 loại thừa số là $x-1$, $x-2$,..., $x-2016$ nên theo nguyên lý Dirichlet, tồn tại một thừa số xuất hiện 2 lần. Thừa số ấy xuất hiện ở cả 2 vế của đẳng thức, dẫn đến việc phương trình nhận được sẽ có nghiệm. Do đó $k\geqslant 2016$

 

Xét phương trình $(x-1)(x-3)...(x-2015)=(x-2)(x-4)...(x-2016)$ $(1)$ nhận được sau khi xoá $k=2016$ thừa số từ đẳng thức ban đầu.

 

Trường hợp $x\in \left \{ 1;2;...;2016 \right \}$ thì phương trình hiển nhiên vô nghiệm.

 

Với $x< 1$ thì $2015-x<2016-x$ ,..., $1-x<2-x$. Cả 2 vế của các bất đẳng thức trên đều dương nên nhân vế theo vế, $VT(1)<VP(1)$. Phương trình vô nghiệm.

 

Với $1<x<2$ thì $VT(1)<0<VP(1)$ nên phương trình cũng vô nghiệm.

 

Với $2<x<3$ thì $2015-x<2016-x$ ,..., $3-x<4-x$, $x-1<x-2$. Cả 2 vế các BĐT trên đều dương nên nhân vế theo vế và đổi dấu, $VT(1)>VP(1)$. Phương trình vô nghiệm.

 

Với $3<x<4$ thì $VT(1)>0>VP(1)$ nên phương trình cũng vô nghiệm.

 

Các trường hợp còn lại ta chứng minh tương tự.

 

Kết luận: Giá trị nhỏ nhất của k là 2016.

 

Mình nghĩ lời giải này chưa đúng, vì sau khi khai triển hết ra thì hệ số của $x^{1008}$ triệt tiêu, so sánh hệ số của $x^{1007}$ 2 vế thì ta thấy $1+3+\ldots+2015< 2+4+\ldots+2016$, do đó đây là phương trình bậc $1007$ và có nghiệm thực. 

 

Lời giải của mình thì xét phương trình $\prod \limits_{i=0}^{503} (x-4i-1)(x-4i-4)=\prod \limits_{i=0}^{503}(x-4i-2)(x-4i-3)$ (1). 

Ta chứng minh rằng $VT(1)<VP(1)$. Chú ý rằng nếu $x<1$, $x>2016$ hoặc $4k<x<4k+1$ thì tất cả các giá trị $(x-4i-1)(x-4i-4)$ và $(x-4i-2)(x-4i-3)$ đều dương, do đó áp dụng bất đẳng thức $(x-4i-1)(x-4i-4)<(x-4i-2)(x-4i-3)$ với mọi $0 \leq i \leq 503$ ta suy ra đpcm.

Ngoài ra, nếu $4k+1<x<4k+2$ hay $4k+3<x<4k+4$ thì dễ thấy $VT(1)<0<VP(1)$. Như vậy ta chỉ cần xét trường hợp tồn tại $k$ sao cho $4k+2<x<4k+3$. Đến đây ta sử dụng bất đẳng thức khác $(x-4i-3)(x-4i-6)<(x-4i-4)(x-4i-5)$ (lúc này tất cả các giá trị $(x-4i-3)(x-4i-6)$ và $(x-4i-4)(x-4i-5)$ đều dương). (2)

Lưu ý là không như trường hợp ở trên, BDT này không quét hết được tất cả các giá trị, mà còn sót lại $(x-1)(x-1008)$ và $(x-2)(x-1007)$. Lúc này do tồn tại $k$ để $4k+2<x<4k+3$ nên $0>(x-2)(x-1007)>(x-1)(x-1008)$. Từ đó ta suy ra $0<\frac{(x-2)(x-1007)}{(x-1)(x-1008)}<1$. (3)

Từ (2) và (3) ta suy ra $0<\frac{VP(1)}{VT(1)}<1$. Tuy nhiên do $4k+2<x<4k+3$ nên cả $VT$ và $VP$ đều âm, từ đó ta suy ra $VT(1)<VP(1)$. 

Vậy $2016$ là giá trị cần tìm.


Bài viết đã được chỉnh sửa nội dung bởi hqdh96: 13-07-2016 - 05:58


#27 JUV

JUV

    Trung sĩ

  • Điều hành viên OLYMPIC
  • 138 Bài viết
  • Giới tính:Nam
  • Đến từ:Nam Định
  • Sở thích:Manga, Music

Đã gửi 13-07-2016 - 06:51

Bài 6:

a/ Xét 1 đoạn thẳng $a$ bất kì và $n-1$ điểm $A_{1};A_{2};...;A_{n-1}$ nằm trên nó, ta sẽ chọn $1$ đầu mút của nó và đánh các số $1;0$ theo thứ tự từ điểm gần chỗ đánh dấu nhất đến điểm xa nhất. Ta chọn đầu mút của đoạn thẳng đang xét ở phía $A_1$. Gọi $d_1;d_2;...;d_{n-1}$ là $n-1$ đoạn thẳng lần lượt đi qua $A_1;A_2;...A_{n-1}$ và lưu ý rằng nếu trong $1$ cách chọn đầu mút của đoạn thẳng $d$ mà điểm $A$ mang số $0$ thì với cách chọn còn lại thì $A$ sẽ mang số $1$ do $n$ lẻ, lúc này ta sẽ chọn đầu mút $n-1$ đoạn thẳng sao cho với $A_{i}$ được đánh số $1$ trên $a$ thì nó sẽ được đánh số $0$ trên $d_i$. Lúc này xét $2$ đoạn thẳng $d_i;d_j$ bất kì. Nếu $A_i$ và $A_j$ đánh số khác nhau trên $a$ thì nó cũng được đánh số khác nhau trên $d_i;d_j$ và có chẵn điểm nằm giữa $A_i$ và $A_j$ trên $a$. Xét $B$ là giao của $d_i;d_j$, lúc này ta thấy rằng nếu $1$ đường thẳng cắt $a$ tại điểm nằm ngoài $A_{i}A_{j}$ thì hoancj đường thẳng đó không cắt $BA_i$ và $BA_j$ hoạc không cắt đoạn nào. Còn $1$ đường thẳng cắt $a$ tại điểm ở giữa $A_i$ và $A_j$ thì nó sẽ cắt $1$ trong $2$ đoạn. Vì có chẵn điểm ở giữa $A_i$ và $A_j$ nên số điểm nằm trên đoạn $BA_i$ và $BA_j$ cùng tính chẵn lẻ. Mà $A_i$ và $A_j$ được đánh số khác nhau trên $d_i;d_j$ nên $B$ cũng được đánh số khác nhau trên $d_i;d_j$.Tương tự trường hợp giữa $A_i;A_j$ có chẵn điểm, chứng minh được giao điểm $2$ đoạn bất kì được đánh số khác nhau trên $2$ đoạn. Mà để con ếch tiến tới số $1$ trên $1$ đoạn thẳng thì cần lẻ lần thổi còi, số $0$ cần chẵn lần. Vì vậy $2$ con ếch không thể gặp nhau

b/(AOPS)Kéo dài $n$ đường thẳng thành $n$ đường thẳng, xét $1$ hình tròn chứa bên trong nó tất cả các giao điểm, hình tròn này cắt $n$ đường thẳng đó tại $2n$ điểm $P_1;P_2;...;P_{2n}$ (Xếp theo chiều KDH). Ta thấy rằng $P_i$ và $P_{i+n}$ cùng nằm trên $1$ đường thẳng với $i\leq n$ và nếu ta chọn $2$ đầu mút là $2$ điểm $P_i$ và $P_{i+1}$ thì $2$ con ếch ở $2$ đầu mút đó sẽ gặp nhau Vì vậy ta chỉ có thể chọn các đầu mút là $P_1;P_3;...;P_{2n-1}$ tuy nhiên khi đó $2$ đầu mút cạnh nhau là $P_{n+1}$ và $P_1$ nên $2$ con ếch ở $2$ đầu mút đó sẽ gặp nhau, tương tự với trường hợp chọn $P_2;P_4;...P_{2n}$, ta đều không thể chọn đầu mút sao cho không có $2$ con ếch nào gặp nhau


Bài viết đã được chỉnh sửa nội dung bởi JUV: 13-07-2016 - 10:58


#28 moonkey01

moonkey01

    Hạ sĩ

  • Thành viên
  • 50 Bài viết
  • Giới tính:Nam
  • Đến từ:PTNK - ĐHQG TP.HCM
  • Sở thích:Hình học, Số học

Đã gửi 13-07-2016 - 08:14

Mình nghĩ lời giải này chưa đúng, vì sau khi khai triển hết ra thì hệ số của $x^{1008}$ triệt tiêu, so sánh hệ số của $x^{1007}$ 2 vế thì ta thấy $1+3+\ldots+2015< 2+4+\ldots+2016$, do đó đây là phương trình bậc $1007$ và có nghiệm thực. 

 

Lời giải của mình thì xét phương trình $\prod \limits_{i=0}^{503} (x-4i-1)(x-4i-4)=\prod \limits_{i=0}^{503}(x-4i-2)(x-4i-3)$ (1). 

Ta chứng minh rằng $VT(1)<VP(1)$. Chú ý rằng nếu $x<1$, $x>2016$ hoặc $4k<x<4k+1$ thì tất cả các giá trị $(x-4i-1)(x-4i-4)$ và $(x-4i-2)(x-4i-3)$ đều dương, do đó áp dụng bất đẳng thức $(x-4i-1)(x-4i-4)<(x-4i-2)(x-4i-3)$ với mọi $0 \leq i \leq 503$ ta suy ra đpcm.

Ngoài ra, nếu $4k+1<x<4k+2$ hay $4k+3<x<4k+4$ thì dễ thấy $VT(1)<0<VP(1)$. Như vậy ta chỉ cần xét trường hợp tồn tại $k$ sao cho $4k+2<x<4k+3$. Đến đây ta sử dụng bất đẳng thức khác $(x-4i-3)(x-4i-6)<(x-4i-4)(x-4i-5)$ (lúc này tất cả các giá trị $(x-4i-3)(x-4i-6)$ và $(x-4i-4)(x-4i-5)$ đều dương). (2)

Lưu ý là không như trường hợp ở trên, BDT này không quét hết được tất cả các giá trị, mà còn sót lại $(x-1)(x-1008)$ và $(x-2)(x-1007)$. Lúc này do tồn tại $k$ để $4k+2<x<4k+3$ nên $0>(x-2)(x-1007)>(x-1)(x-1008)$. Từ đó ta suy ra $0<\frac{(x-2)(x-1007)}{(x-1)(x-1008)}<1$. (3)

Từ (2) và (3) ta suy ra $0<\frac{VP(1)}{VT(1)}<1$. Tuy nhiên do $4k+2<x<4k+3$ nên cả $VT$ và $VP$ đều âm, từ đó ta suy ra $VT(1)<VP(1)$. 

Vậy $2016$ là giá trị cần tìm.

 

Đúng là em bị sai lầm ở đoạn "chứng minh tương tự" thật ! :D Em cảm ơn anh  :icon6:



#29 Zaraki

Zaraki

    PQT

  • Phó Quản trị
  • 4259 Bài viết
  • Giới tính:Nam
  • Đến từ:Đảo mộng mơ.
  • Sở thích:Geometry, Number Theory, Combinatorics, Manga

Đã gửi 13-07-2016 - 11:26

Bài 6:

a/ Xét 1 đoạn thẳng $a$ bất kì và $n-1$ điểm $A_{1};A_{2};...;A_{n-1}$ nằm trên nó, ta sẽ chọn $1$ đầu mút của nó và đánh các số $1;0$ theo thứ tự từ điểm gần chỗ đánh dấu nhất đến điểm xa nhất. Ta chọn đầu mút của đoạn thẳng đang xét ở phía $A_1$. Gọi $d_1;d_2;...;d_{n-1}$ là $n-1$ đoạn thẳng lần lượt đi qua $A_1;A_2;...A_{n-1}$ và lưu ý rằng nếu trong $1$ cách chọn đầu mút của đoạn thẳng $d$ mà điểm $A$ mang số $0$ thì với cách chọn còn lại thì $A$ sẽ mang số $1$ do $n$ lẻ, lúc này ta sẽ chọn đầu mút $n-1$ đoạn thẳng sao cho với $A_{i}$ được đánh số $1$ trên $a$ thì nó sẽ được đánh số $0$ trên $d_i$. Lúc này xét $2$ đoạn thẳng $d_i;d_j$ bất kì. Nếu $A_i$ và $A_j$ đánh số khác nhau trên $a$ thì nó cũng được đánh số khác nhau trên $d_i;d_j$ và có chẵn điểm nằm giữa $A_i$ và $A_j$ trên $a$. Xét $B$ là giao của $d_i;d_j$, lúc này ta thấy rằng nếu $1$ đường thẳng cắt $a$ tại điểm nằm ngoài $A_{i}A_{j}$ thì hoancj đường thẳng đó không cắt $BA_i$ và $BA_j$ hoạc không cắt đoạn nào. Còn $1$ đường thẳng cắt $a$ tại điểm ở giữa $A_i$ và $A_j$ thì nó sẽ cắt $1$ trong $2$ đoạn. Vì có chẵn điểm ở giữa $A_i$ và $A_j$ nên số điểm nằm trên đoạn $BA_i$ và $BA_j$ cùng tính chẵn lẻ. Mà $A_i$ và $A_j$ được đánh số khác nhau trên $d_i;d_j$ nên $B$ cũng được đánh số khác nhau trên $d_i;d_j$.Tương tự trường hợp giữa $A_i;A_j$ có chẵn điểm, chứng minh được giao điểm $2$ đoạn bất kì được đánh số khác nhau trên $2$ đoạn. Mà để con ếch tiến tới số $1$ trên $1$ đoạn thẳng thì cần lẻ lần thổi còi, số $0$ cần chẵn lần. Vì vậy $2$ con ếch không thể gặp nhau

Đúng rồi, câu a mình làm giống JUV. :D


“A man's dream will never end!” - Marshall D. Teach.

#30 quangminhltv99

quangminhltv99

    Hạ sĩ

  • Thành viên
  • 52 Bài viết
  • Giới tính:Nam
  • Đến từ:Hà Nội, Việt Nam
  • Sở thích:Số học, tổ hợp

Đã gửi 13-07-2016 - 19:45

Câu 4: Một tập hợp các số nguyên dương được gọi là tập hương nếu tập đó có ít nhất 2 phần tử và mỗi phần tử của nó có ước nguyên tố chung với ít nhất một trong các phần tử còn lại. Đặt $P(n)=n^2+n+1$. Hãy tìm số nguyên dương $b$ nhỏ nhất sao cho tồn tại số nguyên không âm $a$ để cho tập hợp 

$$\{P(a+1),P(a+2),...,P(a+b)\}$$

là một tập hương.

Lời giải:

Xét trường hợp $b\leq 5$, sử dụng thuật toán Euclid với lưu ý rằng $P(n)$ không chia hết cho $2$ ta có:

$$gcd(P(a+1),P(a+2))=1$$

$$gcd(P(a+1),P(a+3))|7$$

$$gcd(P(a+1),P(a+4))|3$$

$$gcd(P(a+1),P(a+5))|19$$

Cụ thể hơn, $gcd(P(a+1),P(a+3))=7$ tương đương với $a+1\equiv 2 (\mod 7)$, $gcd(P(a+1),P(a+4))=3$ tương đương với $a+1\equiv 1 (\mod 3)$, $gcd(P(a+1),P(a+5))=19$ tương đương với $a+1\equiv 7 (\mod 19)$

Do đó các ước nguyên tố chỉ có thể nằm trong tập hợp $\{3,7,19\}$

Xét một mặt phẳng và 5 điểm $A_1,A_2,...,A_5$ tương ứng với 5 giá trị của $P(a+1),P(a+2),...,P(a+5)$, $A_k$ và $A_l$ được nối với nhau bởi 1 đoạn thẳng có độ dài $3,7,19$ tương ứng với ước nguyên tố chung của $P(a+k)$ và $P(a+l)$ ($A_i$ không thể nối với $A_{i+1}$).

Trường hợp $b=5$:

Nếu $A_1$ nối với $A_5$, khi đó $A_2$ nối với $A_4$ và $A_3$ nối với $A_1$ hoặc $A_5$ (vô lý)

Nếu $A_1$ nối với $A_3$ thì $A_2$ nối với $A_4$ (loại) nên $A_2$ nối với $A_5$, khi đó $A_4$ phải nối với $A_1$, $a$ phải thỏa mãn:

$a\equiv 6 (\mod 7); a\equiv 2 (\mod 3); a\equiv 0 (\mod 3)$ vô lý.

Nếu $A_1$ nối với $A_4$ thì $A_2$ nối với $A_5$ cũng vô lý.

Vậy trường hợp này loại.

Tương tự, ta xét các trường hợp $b=2,3,4$ còn lại suy ra $b\geq 6$

Trường hợp $b=6$, sử dụng định lý Thặng dư Trung Hoa cho hệ sau:

$$a+1\equiv 7 (\mod19)$$

$$a+2\equiv 2 (\mod 7)$$

$$a+3\equiv a+6\equiv 1 (\mod 3)$$

$$a+4\equiv 4 (\mod 7)$$

$$a+5\equiv 11 (\mod 19)$$

Từ đó suy ra $b=6$ là giá trị nhỏ nhất cần tìm

 

Lời giải này giống với lời giải của v_Enhance bên AoPS



#31 Ispectorgadget

Ispectorgadget

    Nothing

  • Quản trị
  • 2936 Bài viết
  • Giới tính:Không khai báo
  • Đến từ:Nơi tình yêu bắt đầu
  • Sở thích:Làm "ai đó" vui

Đã gửi 14-07-2016 - 22:40

Nguồn FB :)) 

Hình gửi kèm

  • imo.jpg
  • ket qua.jpg

►|| The aim of life is self-development. To realize one's nature perfectly - that is what each of us is here for. ™ ♫ Giao diện website du lịch miễn phí Những bí ẩn chưa biết

#32 libach80

libach80

    Hạ sĩ

  • Thành viên
  • 74 Bài viết

Đã gửi 14-07-2016 - 22:47

Cụ thể thế nào anh em nhỉ?







Được gắn nhãn với một hoặc nhiều trong số những từ khóa sau: imo

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

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


    Bing (1)