( Giữa lượt xem của blog và đồ thị hàm số $x^{19}$ )
Thứ Ba, 3 tháng 5, 2016
Khoảnh khắc đẹp
Có gì đó khá giống nhau ở đây :)
( Giữa lượt xem của blog và đồ thị hàm số $x^{19}$ )
( Giữa lượt xem của blog và đồ thị hàm số $x^{19}$ )
Thứ Hai, 2 tháng 5, 2016
Bài toán tổ hợp tô màu
Bài: Vùng nọ có khu đất vàng 100 × 100 m, chia ra làm 100 lô, mỗi lô 10 × 10 m.
Vua bãi rác muốn lấn chiếm khu đất này nên sai tay chân đổ rác vào một số ô. Nếu một ô nào chưa có rác mà có ít nhất hai ô cạnh
nó (có chung cạnh) đã bị đổ rác thì (đáng tiếc) hôm sau nhân dân cũng sẽ đổ rác vào ô đó. Nếu đến một ngày nào đó tất cả các ô
đều bị đổ rác thì vua bãi rác sẽ chiểm khu đất. Nếu vua bãi rác muốn chiếm khu đất này thì lúc đầu cần đổ rác vào ít nhất mấy ô?
Giải
Ta đưa bài toán về mô hình bảng ô vuông kích thước 10 × 10 và mỗi ô bị đổ rác thì sẽ được tô đen. Mỗi bước biến đổi tương ứng với việc ta tô đen một ô chưa được tô và chung cạnh với ít nhất hai ô được tô đen. Do đó, ta chỉ cần tìm số ô đen được tô ban đầu sao cho sau một số hữu hạn bước biến đổi, ta có thể tô đen cả bảng. Gọi p là chu vi của tất cả các phần được tô đen. Ta chứng minh rằng sau mỗi bước biến đổi thì p không tăng. Thật vậy, do ở mỗi bước biến đổi ta tô đen một ô khi nó phải chung cạnh với ít nhất hai ô đen. Ta có các trường hợp sau: Chu vi không đổi, chu vi giảm 2 đơn vị, chu vi giảm 4 đơn vị.
Khi cả bảng được tô đen thì p' = 10 × 4 = 40. Do đó, để tô đen cả bảng ban đầu p ≥ p' = 40. Mà mỗi ô có chu vi là 4. Suy ra ban đầu cần tô ít nhất p/4 = 10 ô. Ta tô mười ô trên cùng một đường chéo chính thì sau hữu hạn bước biến đổi thì cả bảng sẽ được tô đen. Ban đầu vua cho đổ rác vào mười ô trên một đường chéo chính số 1. Ngày hôm sau các ô trên hai đường chéo chính số 2 sẽ bị đổ rác (do mỗi ô đều kề hai ô ở đường chéo số 1). Tiếp tục như vậy thì đến ngày thứ 10 cả khu đất sẽ bị đổ rác. Đáp số: 10 ô.
Giải
Ta đưa bài toán về mô hình bảng ô vuông kích thước 10 × 10 và mỗi ô bị đổ rác thì sẽ được tô đen. Mỗi bước biến đổi tương ứng với việc ta tô đen một ô chưa được tô và chung cạnh với ít nhất hai ô được tô đen. Do đó, ta chỉ cần tìm số ô đen được tô ban đầu sao cho sau một số hữu hạn bước biến đổi, ta có thể tô đen cả bảng. Gọi p là chu vi của tất cả các phần được tô đen. Ta chứng minh rằng sau mỗi bước biến đổi thì p không tăng. Thật vậy, do ở mỗi bước biến đổi ta tô đen một ô khi nó phải chung cạnh với ít nhất hai ô đen. Ta có các trường hợp sau: Chu vi không đổi, chu vi giảm 2 đơn vị, chu vi giảm 4 đơn vị.
Khi cả bảng được tô đen thì p' = 10 × 4 = 40. Do đó, để tô đen cả bảng ban đầu p ≥ p' = 40. Mà mỗi ô có chu vi là 4. Suy ra ban đầu cần tô ít nhất p/4 = 10 ô. Ta tô mười ô trên cùng một đường chéo chính thì sau hữu hạn bước biến đổi thì cả bảng sẽ được tô đen. Ban đầu vua cho đổ rác vào mười ô trên một đường chéo chính số 1. Ngày hôm sau các ô trên hai đường chéo chính số 2 sẽ bị đổ rác (do mỗi ô đều kề hai ô ở đường chéo số 1). Tiếp tục như vậy thì đến ngày thứ 10 cả khu đất sẽ bị đổ rác. Đáp số: 10 ô.
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.
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.
Chủ Nhật, 1 tháng 5, 2016
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
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
Giải.
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ý.
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?
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^*$).
($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).
Đăng ký:
Bài đăng (Atom)