Hai bài số học của Mỹ và Trung Quốc.

1/ (Mỹ) Chứng minh rằng với mỗi số nguyên $n \ge 2$ đều tồn tại một tập S gồm n số nguyên thoả mãn $(a-b)^2$ là ước của ab với mọi a,b thuộc S phân biệt.
2/ ( Trung Quốc) Tìm số nguyên không âm K nhỏ nhất sao cho với mọi tập con K- phần tử của tập hợp {1,2,..50} tồn tại hai phần tử a,b phân biệt mà a+b là ước của ab

Giải

1/ Ta chứng minh bằng quy nạp rằng với mỗi số nguyên dương n đều tồn tại một tập hợp $S_n$ gồm n phần tử thoả mãn điều kiện đã cho.

Với n=2 chọn $S_2$={0,1}. Giả sử khẳng định đã đúng đến n. Ta chứng minh khẳng định đúng với n+1. Gọi L là BCNN của các số khác 0 có dạng $(a-b)^2$ và ab trong đó $a,b \in S_n$. Đặt:

$S_{n+1}$={$s+L: s \in S_n$} $\cup ${0}

Khi đó, vì $L \ge 0$ nên $S_{n+1}$ chứ n+1 phần tử phân biệt không âm. Ta chứng minh tập $S_{n+1}$ thoả mãn.

Lấy u,v, bất kì. Nếu trong u,v có một số bằng 0 thì hiển nhiên. Nếu u,v đều khác 0 thì tồn tại hai phần tử a,b thuộc S sao cho
$u=L+a, v=L+b.$

Từ các chọn ta có $uv \vdots (u-v)^2$. Vậy ta đã chứng minh với n+1. Theo nguyên lí quy nạp ta có đpcm
2/ Giá trị nhỏ nhất của k=39. Cho a,b thuộc S thoả mãn a+b chia hết ab. Đặt $c=(a,b), a=ca_1, b=cb_1$ thì $(a_1,b_1)=1$ Khi đó $c(a_1+b_1)$ chia hết $c^2a_1b_1$ Suy ra $a_1+b_1$ chia hết $ca_1b_1$. Vì $a_1, b_1$ không có ước chung nên $a_1+b_1$ không chia hết $a_1$ và $b_1$. nên c chia hết cho $a_1+b_1$.(1)

Vì S là tập con {1,..,50}, ta có $a+b \le 99$, vì thế $c(a_1+b_1) \le 99$, từ (1) suy ra $a_1+b_1 \le 9$ mặt khác, $a_1+b_1 \ge 3$ từ đây ta tìm được các cặp (a,b):



(6, 3); (12, 6); (18, 9); (24, 12); (30, 15); (36, 18); (42, 21); (48, 24);

(12, 4); (24, 8); (36, 12); (48, 16)

(20, 5), (40, 10), (15, 10), (30, 20), (45, 30)

(30, 6)

(42, 7), (35, 14), (28, 21)

(40, 24)

(45, 36)


Có 23 cặp, 24 số. Còn lại 26 số. Suy ra K>26. Ta cần tìm giá trị nhỏ nhất của K-26 sao cho ta sẽ chọn được hai số trong 24 số thuộc 1 cặp. Ta tìm được giá trị 13 là nhỏ nhất .Thật vậy, giả sử nhỏ hơn 12 thì ta chọn 26 số đó với các số sau đây 3,4,5,7,8,9,10,14,16,28,30,36.


Vậy K nhỏ nhất là 39.

Number theory problem in Israeli Mathematical Olympiad 1995

Problem: The positive integers $d_1, d_2, .. d_n $divide 1995. Prove that there exist $d_i $and $d_j $among them, suach that the numerator of the reduced fraction $d_i$/$d_j $is at least n.

Solution. Note that 3 · 5 · 7 · 19 = 1995. If the chosen divisors include one divisible by 19 and another not divisible by 19, the quotient of the two has numerator divisible by 19, solving the problem since n ≤ 16. If this is not the case, either all divisors are or divisible by 19 or none of them has this property, and in particular n ≤ 8. Without loss of generality, assume the divisors are all not divisible by 19.
Under this assumption, we are done if the divisors include one divisible by 7 and another not divisible by 7, unless n = 8. In the latter case all of the divisors not divisible by 19 occur, including 1 and 3 · 5 · 7, so this case also follows. We now assume that none of the chosen divisors is divisible by 4, so that in particular n ≤ 4.
Again, we are done if the divisors include one divisible by 5 and another not divisible by 5. But this can only fail to occur if n = 1 or n = 2. The former case is trivial, while in the latter case we simply divide the larger divisor by the smaller one, and the resulting numerator has at least one prime divisor and so is at least 3. Hence the problem is solved in all cases

Về câu hình học đề thi Israeli

Đề: Cho PQ là đường kính của đường tròn H. Đường tròn (O) tiếp xúc trong với H và tiếp xúc PQ tại C. Gọi A là điểm trên H và B là một điểm trên PQ sao cho AB vuông PQ và tiếp xúc với (O). Chứng minh rằng AC là phân giác góc PAB.

Giải.

Cách 1: Gọi M là tâm của H. (O) tiếp xúc trong với H tại X, tiếp xúc AB tại Y. Để ý rằng góc PXQ=90 độ

Vậy $QC^2=QX.QY=QB.QP=QA^2$ suy ra $QA=QC$

Lấy đối xứng của C qua Q gọi là C'.

Thì AB là đường đối cực của C' với (O). Suy ra: $(PB,CC')=-1$ ( hoặc có thể chiếu theo điểm A). Vì thế AC là phân giác góc PAB.

Cách 2: Gọi A' đối xứng A qua PQ.
Áp dụng định lý Lyness mở rộng ta có AC đi qua tâm nội tiếp tam giác PAA' mà PB là phân giác góc APA'. Như vậy C là tâm nội tiếp của tam giác.

Vậy AC là phân giác góc PAB.

Nguồn: https://cms.math.ca/crux/v24/n4/page196-207.pdf trang 201

Về hai bài số học trong kì thi vô địch Nga

Bài 1: Tìm số nguyên dương không âm n có đúng 12 ước số, $1=d_1<d_2...<d_{12}=n$ mà $d_{d_4-1}=(d_1+d_2+d_4)d_8$.

Hướng giải.

Theo giả thiết nên tồn tại $i$ sao cho

$d_i=d_1+d_2+d_4$. Vì $d_i >d_4$ nên $13>i>4$

Hiển nhiên ta có: $d_jd_{13-j}=n$ với mọi j và vì $d_id_8=d_{d_4-1}$ suy ra $i \le 5$ vì thế i=5 suy ra $d_4=13$ ta có $d_5=14+d_2$. Do $d_2$ lại là số nguyên tố nhỏ nhất của n mà $d_4=13$

Xét các trường hợp ta có $d_2=3$.

Từ đây dễ dàng tính được $n=1989$ là một nghiệm của bài toán

Bài 2: Tìm tất của các số nguyên dương lẻ n lớn hơn 1 sao cho với mọi a,b là ước của n $(a,b)=1$ thì $a+b-1 $ là ước của n

Hướng giải.

Dễ thấy n là luỹ thừa của một số nguyên tố thì thoả mãn.

Xét $n=p^r.s$ $(p,s)=1$  và p là số nguyên tố nhỏ nhất.

$p+s-1 |n$, xét q là ước nguyên tố của s thì:
$s<p+s-1<s+q$ nên$q \not |p+s-1$. Vì thế $p+s-1=p^c$  suy ra $s=p^c-p+1$ và vì $(p^c,s)=1$ nên $p^c+s-1=2p^c-p | n$. Suy ra $2p^{c-1}-1 | s$ (do không thể là ước của $p^r$) Thay s vào và ta nhận được điều vô lý.

Dùng phép song ánh để chứng minh bài toán tổ hợp- Phần 2

Hôm nay ta tiếp tục dùng phép song ánh để giải bài toán đếm trong tổ hợp.

Ví dụ 2: Cho tập A={1,2,..,2n}. Một tập con B của A gọi là một tập cân nếu trong tập đó số các số chẵn và các số lẻ bằng nhau. ( Tập rỗng là một tập cân). Tính số tập cân của A.

Giải.
Gọi N là họ các tập con của A có đúng n phần tử, B là một tập cân. $B_1, B_2$ tương ứng các tập số chẵn và lẻ của B thì $B_1=B_2$.

Ta xây dựng một ánh xạ như sau;

$f: B \rightarrow  N$

Trong đó $f(B)=B_1 \cup (Y\setminus B_2)$

$\Rightarrow |f(B)|=|B_1|+|Y|-|B_2|$ vậy muốn cho $f(B)$ thuộc $N$ thì trước hết $Y$ phải có n phần tử và Y không có phần tử chung với $B_1$. Như vậy $Y$ phải tập tất cả số lẻ của tập $A$ ($|Y|=n)$

Nên f đơn ánh

Nếu có tập $M$ thuộc $N$. Kí hiệu $M_1$, $M_2$ là tập số chẵn số lẻ của M thì $|M_1|+|M_2|=n$. Ta phải tìm xây dựng $B_1,B_2$ theo $M_1, M_2$ sao cho $|B_1|=|B_2|$ thì $B_2=Y \setminus M_2$ và $B_1=M_1$. $\Rightarrow f(B)=M$.

Như vậy ta xây dựng song ánh giữa B và N.

Vậy A có tấp cả $C^n_{2n}$

Nhận xét: Tại sao lại xây dựng f đi từ B đến N ? Thực ra qua một vài phép liệt kê ta sẽ thấy !
Một số bài tập cho bạn đọc:

1/(Bài toán chia kẹo của Euler) Có m chiếc kẹo giống nhau chia cho n em bé. Hỏi có bao nhiêu cách chia?

Đây cũng chính là bài toán: “Tìm số nghiệm không âm của phương trình :  ($n, m \in N^*$). 

Các bạn có thể nghiên cứu chuyên đề tại đây.

2( Lấy trong TLCT)/ Cho trước số nguyên dương n và số nguyên dương r thoả $r<n-r+1$. Giả sử X={1,2..n}. Hoi r có bao nhiêu tập con A của X đồng thời có tính chất:

+ Chứa r phần tử

+ Không chứa hai số nguyên liên tiếp.

(Gợi ý: Các bạn thử liệt kê như Vd 2 các bạn sẽ có hướng làm). 

Hai bài toán hình học nổi tiếng trong kì thi IMO

Đây là hai bài hình học trong kì thi toán Quốc tế được thầy Trần Quang Hùng đánh giá là đặc biệt và hay trong 7 bài hình học mà thầy đăng

Bài toán 1 (IMO 1985 bài 5 ngày 2). Đường tròn với tâm O đi qua các đỉnh A và C của tam giác ABC cắt các đoạn thẳng BA,BC lần thứ hai tại các điểm K và N. Gọi M là giao điểm của các đường tròn ngoại tiếp tam giác ABC và KBN (khác B). Chứng minh rằng $∠OMB=90^o$.


Bài toán 2 (IMO 1996 bài 2 ngày 1). Cho điểm P nằm trong tam giác ABC sao cho ∠APB−∠ACB=∠APC−∠ABC. Gọi D,E lần lượt là tâm nội tiếp các tam giác APB,APC. Chứng minh rằng AP,BD,CE đồng quy.

Tôi xin trình bày tắt lời giải của hai bài toán.

Bài toán 1: Gọi P là giao điểm các đường thẳng AC và KN thì 4 điểm M, P, A, K cùng thuộc một đường tròn (theo định lý Miquel) ngoài ra ta cũng có M nằm trên đoạn BP.

Theo phương tích ta có:

$BO^2-PO^2=BO^2-R^2-(PO^2-R^2)=\overline{BM}.\overline{BP}-\overline{PM}.\overline{PB}=BM^2-PM^2$

Theo định lí 4 điểm ta có điều phải chứng minh.

Bài toán 2:  Ta sẽ sử dụng bổ đề: Cho P là một điểm năm trong tam giác ABC. X,Y,Z lần lượt là chân đường vuông góc hạ từ P xuống BC, CA, AB.

Khi đó:$ PA=\dfrac{YZ}{sin A}$ và $\angle APB-\angle ACB=\angle XZY$

Bổ đề này xin dành cho bạn đọc chứng minh.

Trở lại bài toán. Ta có: $\angle APB-\angle ACB=\angle XZY$ và $\angle APC-\angle ABC=\angle XYZ$

Suy ra tam giác XYZ cân, với XY=XZ. Từ đó:

$PCsinACB=PB.sin ABC$ dùng thêm định lí hàm sin ta được

$\dfrac{AB}{PB}=\dfrac{AC}{PC}$

Nếu BD cắt AP tại W thì theo định lí Stewwart ta có $\dfrac{AB}{PB}=\dfrac{AC}{PC}=\dfrac{AW}{PW}$ và CW cũng là phân giác, ta có điều phải chứng minh.

Dùng phép song ánh để giải bài toán tổ hợp-Phần 1

Đối với một số bài tổ hợp đếm, thì thay vì đếm theo đề bài rất khó khăn ta có thể đếm bằng cách xây dựng một song ánh và áp dụng tính chất:
"Nếu có một phép song ánh đi từ tập X đến tập Y thì |X|=|Y| (trong đó X, Y là hai tập hữu hạn)". Và chuyển về một bài toán đơn giản hơn để tính toán.

Ví dụ: Gọi N là tất cả các số viết trong hệ thập phân có n chữ số trong đó chỉ có các chữ số 1,2,3,4 và số chữ số 1 bằng số chữ số 2. Tính |N|

Giải

Ta bắt đầu xây dựng một phép song ánh:

Gọi M là các số nguyên dương viết trong hệ thập phân có 2n chữ số, trong đó có n chữ số 1 và n chữ số 2. Ta sẽ chứng minh |M|=|N|

Với mỗi số có n chữ số gồm các chữ số 1,2,3,4 và số chữ số 1 bằng số chữ số 2, ta nhân đôi thành số có 2n chữ số theo quy tắc sau: đầu tiên, hai phiên bản của số này được viết kề nhau thành số có có 2 chữ số, sau đó các chữ số 3 ở n chữ số đầu và các chữ số 4 ở n chữ số sau được đổi thành chữ số 1, các chữ số 3 ở n chữ số sau và các chữ số 4 ở n chữ số đầu được đổi thành chữ số 2.

Như thế ta thu được một số có đúng n chữ số 1 và n chữ số 2. Rõ ràng đây là một đơn ánh. Ta thấy với mỗi phần tử thuộc M đều được xác định bởi 1 phần tử N bằng cách ta cắt n chữ số đầu và n chữ số còn lại rồi cộng theo quy tắc 1+1=1, 2+2=2, 1+2=3, 2+1=4, và ta thu được các số gồm các chữ số 1,2,3,4 với số chữ số 1 bằng số chữ số 2.

Vậy ta có |M|=|N|

Số phần tử của |M|=$2^n.C^n_{2n}$ nên $|N|=2^n.C^n_{2n}$.

Như vậy qua phép song ánh ta đã đếm số phần tử của N bằng cách đơn giản hơn do chỉ cần đếm số phần tử của tập M.

Sở dĩ có phép cộng trên là do ta đã sử dụng đơn ánh để xây dựng tính chất từ $M$ sang $N$.