|
|
|
Ngoài một số quy định đã được nêu trong phần Quy định của Ghi Danh , mọi người tranh thủ bỏ ra 5 phút để đọc thêm một số Quy định sau để khỏi bị treo nick ở MathScope nhé ! * Quy định về việc viết bài trong diễn đàn MathScope * Nếu bạn muốn gia nhập đội ngũ BQT thì vui lòng tham gia tại đây |
| Ðiều Chỉnh | Xếp Bài |
11-01-2013, 03:21 PM | #16 |
+Thành Viên+ Tham gia ngày: Sep 2012 Bài gởi: 7 Thanks: 0 Thanked 5 Times in 2 Posts | Mình có cách này ngắn gọn hơn cho câu a) . Vì ban đầu dãy có 2 số 1 và 1000 nên sau n lần thì mỗi số được viết trên đường thằng đều có dạng b + a.1000 với a, b <= n và a, b là số tự nhiên khác 0 và các cặp số ( a, b ) là duy nhất mà b + 1000a = 2013 nên chỉ có 2 khả năng a = 1 hoặc a = 2 ứng với b = 1013 và b =2013. Vậy 2013 chỉ xuất hiện đúng 2 lần trên đường thằng. |
11-01-2013, 03:28 PM | #17 | |
+Thành Viên+ Tham gia ngày: Aug 2011 Đến từ: Mù Cang Chải Bài gởi: 33 Thanks: 34 Thanked 11 Times in 4 Posts | Trích:
| |
11-01-2013, 05:16 PM | #18 |
+Thành Viên+ Tham gia ngày: Dec 2011 Bài gởi: 12 Thanks: 51 Thanked 22 Times in 1 Post | Mình cũng làm ra hai lần. Mới đầu tưởng dùng bất biến nhưng hóa ra suy luận bình thường |
11-01-2013, 05:52 PM | #19 | |
+Thành Viên+ Tham gia ngày: Sep 2010 Bài gởi: 5 Thanks: 0 Thanked 1 Time in 1 Post | Trích:
| |
11-01-2013, 05:54 PM | #20 |
Administrator | Câu 4b thì mình mới có ý tưởng thế này nhưng chưa ra được. Đặt F(a,b,i) là số lần số 2013 xuất hiện trong dãy nhận được từ 2 số hạng đầu là a và b sau i lần thực hiện thao tác. Ta có các nhận xét sau: (1) $F(a,b,i)=F(a,a+b,i-1)+F(a+b,b,i-1)$ với $i > 1$. (2) $F(a,b,i)=F(b,a,i).$ (3) $F(a,b,i)=0$ nếu phương trình $ax+by=2013$ không có nghiệm nguyên dương. Trong dãy từ 1, 2, 3, ..., 1000 đã cho. Ta thấy rằng sau lần thứ 2 thì các số mới được sinh ra từ các cặp $(1,2), (2,3),...,(999,1000)$ nằm rời nhau và có ranh giới là các số cũ đã có.Ta cần tính $\sum_{i=1}^{999} F(i,i+1,2013)$. Tuy nhiên, tổng này sẽ có liên quan đến$F(i,i+1,2013)$ với $1 \le i \le 2012$ nên ta cần tìm mối liên hệ truy hồi (giảm giá trị của thành phần thứ 3 xuống) giữa các số có dạng như thế. Chẳng hạn như ở câu a, ta đã tính được $F(1,1000,8)=1, F(1,1000,k)=2, k \ge 1003$. Nếu bài này giải được theo cách này thì có lẽ cần phải tìm thêm một nhận xét quan trọng nữa mới có thể xử lí được. __________________ Sự im lặng của bầy mèo thay đổi nội dung bởi: huynhcongbang, 11-01-2013 lúc 06:13 PM |
11-01-2013, 08:29 PM | #21 |
+Thành Viên+ Tham gia ngày: Sep 2011 Đến từ: no*i ty bă't đâ'u Bài gởi: 695 Thanks: 121 Thanked 335 Times in 214 Posts | Có ai hoàn thiện được bài 4b chưa nhỉ, mình cay bài này quá __________________ |
11-01-2013, 11:55 PM | #22 |
+Thành Viên+ Tham gia ngày: Nov 2010 Đến từ: THPT chuyên Vĩnh Phúc Bài gởi: 570 Thanks: 24 Thanked 537 Times in 263 Posts | Câu 4b. Ta cần các kết quả liên quan đến dãy Farey (có thể tham khảo [Only registered and activated users can see links. ]) Kí hiệu $F_n $ là tập hợp các phân số Farey có mẫu không vượt quá Xét 2 số nguyên dương $a_1, a_2, a_1<a_2 $. Khi đó ta sẽ xét cách điền số theo quy tắc của đề bài thì phải điền các số có dạng $ma_1+na_2 $ mỗi số này ta gọi có hệ số là $(m,n) $ Bước 1: $a_1, a_1+a_2, a_2 $ dãy hệ số là $(1,0), (1,1), (0,1) $ tương ứng với $F_1 $ Bước 2: $a_1, 2a_1+a_2, a_1+a_2, a_1+2a_2, a_2 $ hệ số là $(1,0), (2,1),(1,1),(1,2),(0,1) $ tương ứng $F_2 $ Bước 3: Ta được $(1,0), (3,1),(2,1)(3,2),(1,1),(2,3),(1,3),(1,2),(2,3),(1, 1) $ ứng với $F_3 $ Bước 4: Ta được $(1,0),(4,1) (3,1),(5,2)(2,1)(5,3)(3,2),(4,3)(1,1),(3,4)(2,3),( 3,5)(1,2)(2,5)(1,3),(1,4),(0,1) $ tương ứng với $F_4 $ Bằng quy nạp thì dãy hệ số ở bước thứ $n $ tương ứng với $F_n $ Bây giờ ta sẽ tìm số lần xuất hiện số 2013 trên các đoạn $[n;n+1] $ Nhận xét mỗi phân số ${p}/{q} $ trong dãy $F_n $ có tính chất $gcd(p,q)=1, p\le q $. +) Xét trên đoạn $[n,n+1] $ nếu số $2013 $ xuất hiện thì phải tồn tại phân số ${p}/{q} $ của $F_{2012} $ và $q<2013 $ sao cho $np+(n+1)q=2013 $ hoặc $nq+(n+1)p=2013 $ ta đếm số nghiệm của các phương trình này với điều kiện $gcd(p,q)=1, p\le q $ +) Ta đếm số nghiệm của pt $np+(n+1)q=2013 $ với $gcd(p,q)=1 $ (1). Số nghiệm của phương trình này với điều kiện $gcd(p,q)=1 $ bằng số nghiệm của phương trình $nr+q=2013 $ với điều kiện $gcd(q,r)=1, q<r $. Với điều kiện $gcd(r,q)=1, q\ge 1 $ ta được $\left[ {\frac{{2013}}{{n + 1}}} \right] + 1 \le r \le \left[ {\frac{{2012}}{n}} \right] $. Muốn nghiệm thỏa mãn điều kiện $gcd(r,q)=1 $ thì $r $ không chia hết cho 3 hoặc 11 hoặc 61. Dùng nguyên lí bù trừ ta được số lượng các số từ 1 đến k chia hết cho 3 hoặc 11 hoặc 61 là $A(k)=\left[ {\frac{k}{3}} \right] + \left[ {\frac{k}{{11}}} \right] + \left[ {\frac{k}{{61}}} \right] - \left[ {\frac{k}{{33}}} \right] - \left[ {\frac{k}{{671}}} \right] - \left[ {\frac{k}{{183}}} \right] + \left[ {\frac{k}{{2013}}} \right] $. Do đó số lượng $r $ là ${\left[ {\frac{{2012}}{n}} \right]} - A\left( {\left[ {\frac{{2012}}{n}} \right]} \right) + A\left( {\left[ {\frac{{2013}}{{n + 1}}} \right] + 1} \right) $ và đây cũng chính là số nghiệm của (1). Vậy số lần xuất hiện 2013 là $$\sum\limits_{n = 1}^{999} {\left( {{\left[ {\frac{{2012}}{n}} \right]} - A\left( {\left[ {\frac{{2012}}{n}} \right]} \right) + A\left( {\left[ {\frac{{2013}}{{n + 1}}} \right] + 1} \right)} \right)} $ $ thay đổi nội dung bởi: ThangToan, 12-01-2013 lúc 04:02 AM |
The Following 16 Users Say Thank You to ThangToan For This Useful Post: | 5434 (13-01-2013), bboy114crew (12-01-2013), Gin Mellkior (22-01-2013), ha.uyen2796 (13-01-2013), hayhayhoho (14-01-2013), hoanghaithanh (13-01-2013), huynhcongbang (12-01-2013), kien10a1 (13-01-2013), let_wind_go (12-01-2013), luugiangnam (12-01-2013), Mr.T.A. (12-01-2013), nghiepdu-socap (13-01-2013), ntuan5 (12-01-2013), perfectstrong (12-01-2013), quoc_hocpro (13-01-2013), thaygiaocht (12-01-2013) |
12-01-2013, 12:53 AM | #23 |
Moderator Tham gia ngày: Nov 2007 Đến từ: cyber world Bài gởi: 413 Thanks: 14 Thanked 466 Times in 171 Posts | Trước hết ta xét dãy $a_1,...,a_{2^N+1) $thu được sau 2013 bước với hai số ban đầu là $0,1 $. Ở đây $N = 2013 $. "Dễ dàng" chứng minh bằng quy nạp điều sau: Với mọi cặp $m,n $ mà $1\le m,n\le N $ và $(m,n) = 1 $, tồn tại duy nhất $1\le i\le 2^{N}+1 $sao cho: $a_i = m $ và $a_{2^N+2-i} = n $. (Sử dụng thuật toán Euclit) và tính chất của dãy $a_i $. Có thể xét nếu $(m,n) = 1 $ và $m>n $, ta xét cặp $m-n,n $ thì $(m-n,n) $, theo giả thiết quy nạp thì $1\le i\le 2^{N-1}+1 $ sao cho $a_i = m-n $ và $a_{2^{N-1}+2-i} = n $... Kết quả của bài toán chính là số các bộ $1\le k\le 999 $, $1\le a,b\le 2013 $, $(a,b) = 1 $ mà $ka + (k+1)b = 2013 $. __________________ Traum is giấc mơ. thay đổi nội dung bởi: Traum, 12-01-2013 lúc 04:29 AM |
The Following 7 Users Say Thank You to Traum For This Useful Post: | 5434 (13-01-2013), bboy114crew (12-01-2013), hayhayhoho (14-01-2013), hoanghaithanh (13-01-2013), huynhcongbang (12-01-2013), kien10a1 (13-01-2013), nghiepdu-socap (13-01-2013) |
12-01-2013, 03:26 AM | #24 |
Administrator | Nếu như theo cách của thầy Thắng và anh Traum thì đáp số bài toán là 1198 (nếu tính được cái này thì quá tốt). Bên dưới là đoạn chương trình chạy thử để kiểm tra. __________________ Sự im lặng của bầy mèo thay đổi nội dung bởi: huynhcongbang, 12-01-2013 lúc 03:56 AM |
The Following User Says Thank You to huynhcongbang For This Useful Post: | ThangToan (12-01-2013) |
12-01-2013, 04:25 AM | #25 |
+Thành Viên+ Tham gia ngày: Nov 2010 Đến từ: THPT chuyên Vĩnh Phúc Bài gởi: 570 Thanks: 24 Thanked 537 Times in 263 Posts | Câu 4a. số $2013 $ sẽ tương ứng với hệ số $(p,q) $ hoặc $(q, p) $ trong đó $\frac {p}{q}, gcd(p,q)=1, p\le q $ là một phân số Farey. Khi đó ta có phương trình $p+1000q=2013 $ hoặc $q+1000p=2013 $ sẽ chỉ có 2 nghiệm là $(p,q)=(1,1013), (2,13) $. Do đó 2013 phải xuất hiện đúng 2 lần. Câu 4a này một số bạn làm ở trên là chưa chính xác. |
The Following 5 Users Say Thank You to ThangToan For This Useful Post: | Gin Mellkior (22-01-2013), ha.uyen2796 (13-01-2013), hoanghaithanh (13-01-2013), huynhcongbang (12-01-2013), Mr.T.A. (13-01-2013) |
12-01-2013, 06:21 AM | #26 |
Administrator | Ở câu b này, mình nghĩ là sẽ có một số bạn nhận xét được 2 vấn đề như sau: - Các số sinh ra từ dãy $1, 2, 3, ..., 1000$ ban đầu sẽ nằm rời nhau giữa các cặp số $(1,2), (2,3), ..., (999, 1000)$ ban đầu. Do đó, ta chỉ cần xét đại diện khoảng $(k,k+1), 1 \le k \le 999$ rồi tính tổng. - Các số trong mỗi khoảng $(a,b)$ sẽ có dạng $xa+yb$ và ta cần đếm số nghiệm nguyên dương $(x,y)$ của phương trình $xa+yb=2013$. Tuy nhiên, cần phải có ràng buộc vì không phải nghiệm nào của phương trình này cũng tương ứng với một số có trong dãy sinh ra theo đề bài. Thêm nữa, nếu $(x,y)$ thỏa mãn thì có phải bộ số này là duy nhất hay không. Theo mình thì hai lời giải ở trên của thầy ThangToan và anh Traum nói chung đã xử lí được vấn đề này. Chú ý định nghĩa của dãy Farey là: Dãy Farey của một số nguyên dương $n$, kí hiệu $F_n$ là dãy tăng các phân số trong đoạn [0,1] sao cho chúng là các phân số tối giản có dạng $\frac{a}{b}$ với $0 \le a \le b \le n, a, b \in \mathbb{Z}$. Phân số đầu tiên của dãy có giá trị 0 và ta quy định viết 0/1, phân số cuối cùng của dãy có giá trị 1 và ta quy định viết 1/1. Nếu làm theo hướng này thì có thể không cần chứng minh lại nhiều thứ vì nội dung này có giới thiệu khá nhiều trong cuốn Tài liệu giáo khoa chuyên Toán 11. Mình xin cụ thể hóa lời giải của anh Traum ở trên. Trước hết, ta thấy rằng với mỗi dãy có $k$ số thì sau một bước thực hiện, nó sẽ có thêm $k-1$ số. Do đó, với dãy ban đầu có 2 số, bằng quy nạp, ta chứng minh được rằng dãy số thứ $n$ sẽ có $2^n+1$ số. Xét dãy số sinh bởi 2 phần tử đầu là $(1,0)$ thì sau $n$ bước, các phần tử nhận được là $a_1, a_2, ..., a_{2^n+1}$ (ở đây ta quan tâm đến $n=2013$). Chẳng hạn với $n=1$, ta có dãy 1 1 0 và $n=3$, ta có dãy 1 3 2 3 1 2 1 1 0. Xét dãy sinh bởi hai phần tử đầu là $(u, v)$ và sau $n$ bước, các phần tử nhận được là $b_1, b_2, ..., b_{2^n+1}$. Ta sẽ chứng minh rằng $b_i =u \cdot a_i +v \cdot a_{2^n+2-i}$ với $1 \le i \le 2^n+1$. (*) Chứng minh có thể thực hiện bằng quy nạp theo $n$. - Sau bước 1, ta có 3 số $u,u+v,v$ và dễ dàng kiểm tra được (*) đúng. - Giả sử (*) đúng đến bước thứ $n$, ta sẽ chứng minh nó cũng đúng với $n+1$. Thật vậy, Giả sử với hai số hạng đầu là $(1,0)$ và $(u,v)$ thì 2 dãy tương ứng nhận được ở bước thứ $n+1$ là: $c_1, c_2, ..., c_{2^{n+1}}+1$ và $d_1, d_2, ..., d_{2^{n+1}}+1$ Rõ ràng theo quy luật sinh dãy số của đề bài thì:$c_{2k-1} = a_k, c_{2k} = a_{k}+a_{k+1}, d_{2k-1}=b_k, d_{2k} = b_{k}+b_{k+1}, $ với $1 \le k \le 2^{n}$. Theo giả thiết quy nạp, ta có $d_{2k+1} = b_k = u \cdot a_k +v \cdot a_{2^n+2-k} = u \cdot c_{2k+1} +v \cdot c_{2^{n+1}+2-(2k+1)}$ Tương tự, ta cũng có $d_{2k} = u \cdot c_{2k} +v \cdot c_{2^{n+1}+2-2k}$. Do đó, (*) cũng đúng với $n+1$ nên (*) được chứng minh. Gọi $S_k$ là số các số 2013 có trong dãy các số đã cho sau 2013 với hãy số đầu tiên là $(k, k+1)$ thì số cần tìm là $\sum_{k=1}^{999}S_k$ bởi vì từ bước 1 trở đi, các số được sinh ra tiếp theo đều nằm rời nhau giữa các cặp số $(1,2), (2,3), ..., (999, 1000)$ ban đầu. Rõ ràng, các số sinh ra bởi hai số $k, k+1$ có dạng $ak+b(k+1)$ nên ta cần đếm số bộ số nguyên dương $(a,b)$ mà $ak+b(k+1)=2013$. Ta sẽ chứng minh rằng số bộ đó chính là số nghiệm nguyên dương của phương trình $ak+b(k+1)=2013$ và $(a,b)=1$ bằng cách chỉ ra rằng, với mỗi bộ $(a,b)$ mà $(a,b)=1$ thì tồn tại đúng một chỉ số $i, 1 \le i \le 2^n+1$ mà $a_i = a, a_{2^n+2-i}=b$; đồng thời, $(a_i, a_{2^n+2-i})=1$ với mọi $i$. Từ đó suy ra $S_i$ chính là số bộ $(a,b)$ mà $ak+b(k+1)=2013$ và $(a,b)=1$. Số lượng số cần tính chính là $\sum_{k=1}^{999}S_k$. __________________ Sự im lặng của bầy mèo thay đổi nội dung bởi: huynhcongbang, 12-01-2013 lúc 06:31 AM |
The Following 7 Users Say Thank You to huynhcongbang For This Useful Post: | 5434 (13-01-2013), bboy114crew (12-01-2013), congbang_dhsp (04-02-2013), hphnna (12-01-2013), kien10a1 (13-01-2013), nghiepdu-socap (13-01-2013), Traum (12-01-2013) |
12-01-2013, 06:42 AM | #27 | |
Moderator Tham gia ngày: Nov 2007 Đến từ: cyber world Bài gởi: 413 Thanks: 14 Thanked 466 Times in 171 Posts | Trích:
Ta có $ka + (k+1)b = 2013 $ và $(a,b) = 1 $ nên $(2013,k(a+b)) = 1 $. Ta chứng minh rằng với mọi $3\le p < 2013 $ mà $(p,2013) = 1 $ thì tồn tại duy nhất $1\le a,b\le 2013, 1\le k\le 999 $ mà $(a,b) = 1 $ và $a + b = p $ và $kp + b = 2013 $. Thật vậy tồn tại duy nhất $1\le k\le 999 $ sao cho $\frac{2013}{k+1} < p < \frac{2013}{k} $. Đặt $b = 2013 - kp $ thì ta có $0 < b < p $ . Tiếp theo đặt $a = p-b $. Dễ chứng minh rằng $(a,b) = 1 $, $a+ b = p $ và $ka + (k+1)b = 2013 $. Có thể chứng minh điều ngược lại cũng đúng. Vậy số cần tìm là $\phi(2013) - 2 = 1200 - 2 = 1198 $ __________________ Traum is giấc mơ. thay đổi nội dung bởi: Traum, 12-01-2013 lúc 06:47 AM | |
The Following 11 Users Say Thank You to Traum For This Useful Post: | 5434 (13-01-2013), bboy114crew (12-01-2013), huynhcongbang (12-01-2013), let_wind_go (12-01-2013), lexuanthang (12-01-2013), nghiepdu-socap (13-01-2013), ntuan5 (12-01-2013), perfectstrong (12-01-2013), quangvinht2 (12-01-2013), quoc_hocpro (13-01-2013), thaygiaocht (12-01-2013) |
13-01-2013, 09:16 AM | #28 |
+Thành Viên+ Tham gia ngày: Apr 2010 Bài gởi: 193 Thanks: 195 Thanked 129 Times in 72 Posts | Có một cách rút gọn khác như sau ạ Gọi $S_n $ là số lần xuất hiện của 2013 nếu 2 số hạng đầu là n,n+1 $T_n $ là số lần xuất hiền của 2013 nếu 2 số hạng đầu là 1,n Khi đó ta có hệ thức sau $T_n=S_n+T_{n+1} $ Suy ra $T_2=S_2+S_3+...+S_n+T_{n+1} \Rightarrow 2S_1=S_1+....+S_n+T_{n+1} $ Kết quả bài toán là $S_1+....+S_{999}=2S_1-T_{1000}=2S_1-2 $ ( theo câu a) Mặt khác $S_1 $ chính là số bộ nghiệm của phương trình $2013=x+2y=(x+y)+y,1 \le x,y \le 2013,(x,y)=1 $ và bằng $\frac{\phi{(2013)}}{2} $ Vậy đáp số là $\phi{(2013)}-2=1198 $ Tổng quát cho số 2013 và 1000 bởi m,n thì đáp số là $\phi{(m)}-T_n $ mà cách để tính $T_n $ cho đẹp thì em vẫn chưa nghĩ ra |
The Following 10 Users Say Thank You to nghiepdu-socap For This Useful Post: | 5434 (13-01-2013), hieu1411997 (13-01-2013), huynhcongbang (13-01-2013), kien10a1 (13-01-2013), quoc_hocpro (13-01-2013), thaygiaocht (13-01-2013), TNP (13-01-2013), tqdungt1k20 (13-01-2013), transonlvt (13-01-2013), vinhhop.qt (14-01-2013) |
13-01-2013, 10:05 PM | #29 |
+Thành Viên+ Tham gia ngày: Mar 2011 Bài gởi: 38 Thanks: 3 Thanked 30 Times in 16 Posts | Ý a có đc đến 2 điểm không mọi người? |
14-01-2013, 02:36 PM | #30 | ||
Administrator | Trích:
Từ công thức truy hồi $T_n=S_n+T_{n+1} $, anh đoán là em lập luận thế này: Với 2 số hạng đầu là $(1,n) $, sau 1 lần thực hiện, chúng sẽ là $(1,n+1) $ và $(n,n+1) $, tương ứng với $T_{n+1}, S_n $ nên có được điều trên. Tuy nhiên, khi đó thì số lần thực hiện trên $(1,n+1) $ và $(n,n+1) $ ít hơn số lần thực hiện trên $(1,n) $ 1 lần nên đẳng thức trên có đảm bảo đúng không? ------------------------------ Theo mình nghĩ thì ý a của bài này sẽ được từ 1 đến 1,5 điểm. ------------------------------ Trích:
http://forum.mathscope.org/showthread.php?t=17326 __________________ Sự im lặng của bầy mèo thay đổi nội dung bởi: huynhcongbang, 14-01-2013 lúc 02:49 PM Lý do: Tự động gộp bài | ||
The Following 3 Users Say Thank You to huynhcongbang For This Useful Post: |
Bookmarks |
Ðiều Chỉnh | |
Xếp Bài | |
|
|