|
|
|
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 |
09-07-2014, 08:44 PM | #1 |
+Thành Viên Danh Dự+ | [IMO 2014] Bài 5 - Tổ hợp Nguồn: facebook thầy Lê Anh Vinh __________________ Hope against hope. thay đổi nội dung bởi: Fool's theorem, 09-07-2014 lúc 08:46 PM |
The Following User Says Thank You to Fool's theorem For This Useful Post: | thiendieu96 (10-07-2014) |
10-07-2014, 04:05 AM | #2 |
Administrator | Bài này được tính vào dạng tổ hợp chứ không phải số học như phân loại của Jury. Một ý tưởng tự nhiên là chứng minh mệnh đề tổng quát: Nếu có các đồng tiền tổng mệnh giá không quá k - 1/2 thì có thể chia các đồng tiền thành k nhóm, mỗi nhóm có tổng mệnh giá không quá 1. Và ý tưởng tự nhiên là chứng minh bằng quy nạp. Tuy nhiên, có một lời giải rất đẹp dùng ý tưởng phản ví dụ nhỏ nhất. Lời giải này do Fedor Petrov (Nga) đề xuất. Giả sử n là số nhỏ nhất mà mệnh đề không đúng, tức là tồn tại một số đồng tiền có tổng mệnh giá không quá n-1/2 nhưng không chia được thành n nhóm, mỗi nhóm có tổng mệnh giá không quá 1. Khi đó trong tất cả các phản ví dụ với giá trị n này, ta chọn phản ví dụ với số lượng tiền nhỏ nhất. Gọi m là đồng tiền nhẹ nhất. Theo tính nhỏ nhất, ta có thể chia các đồng tiền còn lại thành n nhóm, mỗi nhóm không vượt quá 1 nhưng lại lớn hơn 1-m (vì nếu có nhóm <=1-m thì ta có thể bổ sung đồng tiền trọng lượng m vào đó). Vậy ta có n-1/2 > n(1-m) + m, suy ra m > 1/(2n-2). Tiếp theo, nếu có 2 đồng tiền mệnh giá 1/2k thì ta có thể thay bằng 1 đồng tiền mệnh giá 1/k trái với tính nhỏ nhất của số đồng tiền. Tương tự, nếu có p đồng tiền mệnh giá 1/p thì ta có thể bỏ p đồng tiền này đi. Nhóm còn lại sẽ không thể chia được thành n-1 nhóm, mỗi nhóm có tổng mệnh giá không vượt quá 1 (nếu chia được thì các đồng tiền cũ cũng chia được). Mâu thuẫn với tính nhỏ nhất của n. Vậy tổng mệnh giá các đồng tiền sẽ nhỏ hơn: 1/2 + 1/3 + 1/3 + 1/4 + 1/5 + 1/5 + 1/5 + 1/5 + 1/6 + ... + 1/(2n-2) < 1/2 + 3/3 + 5/5 + .... + (2n-3)/(2n-3) = n - 3/2 và như vậy phản ví dụ này đúng cho n-1, mâu thuẫn. |
The Following 4 Users Say Thank You to namdung For This Useful Post: |
10-07-2014, 10:50 AM | #3 |
+Thành Viên+ Tham gia ngày: Jul 2011 Bài gởi: 10 Thanks: 7 Thanked 6 Times in 3 Posts | Ta sẽ chứng minh bằng quy nạp rằng nếu số tiền không vượt quá $n-\frac{1}{2}$ thì có thể chia số tiền này vào n chiếc túi mà mỗi túi có số tiền không vượt quá 1 dễ thấy bài toán đúng với n=1,2 Giả sử bài toán đúng với tổng số tiền là $n-1-\frac{1}{2}$ Đầu tiên ta thực hiện liên tiếp việc ghép tiền như sau: nếu có 2 đồng có mệnh giá $\frac{1}{2k}$ ta sẽ ghép vào nhau và coi nó là 1 đồng $\frac{1}{k}$ Sau khi thực hiện ta gọi $a_i$ là số lượng đồng tiền có mệnh giá $\frac{1}{i}$ (với i=1,2,3,...) Sau công việc ghép tiền trên rõ ràng $a_{2k} \le 1$, với mọi k Nếu tồn tại số i mà $a_i \ge i$ lúc này ta sẽ đưa i đồng mệnh giá vào 1 túi, số tiền còn lại lúc này không vượt quá $n-1-\frac{1}{2}$, theo phía trên số tiền này có thể chia vào (n-1) túi mà mỗi túi có tổng tiền không vượt quá 1 và ta đã có cách chia số tiền không vượt quá $n-\frac{1}{2}$ vào n túi mà mỗi túi có số tiền không vượt quá 1 Xét trường hợp còn lại: $a_i \le i-1$ với mọi số nguyên dương i Với i=1,2,...,n ta sẽ cho vào túi i tất cả các đồng tiền với mệnh giá dạng $\frac{1}{(2i-1)2^{k}}$ (k là số tự nhiên), lúc này tổng số tiền của túi i không vượt quá $\frac{1}{2i-1}(a_{2i-1}+\frac{1}{2}+\frac{1}{2^2}+...+\frac{1}{2^p})<1$ (p là một số hữu hạn) Sau khi cho tiền vào túi theo cách trên dễ thấy lúc này các đồng tiền còn lại sẽ có mệnh giá là $\frac{1}{k}$ với k>2n. Ta sẽ bỏ nó vào các túi theo cách sau: Nếu trong các túi có túi có số tiền không quá $1-\frac{1}{2n}$ ta sẽ thêm lần lượt từng đồng một vào túi đó cho đến khi túi đó có số tiền vượt quá $1-\frac{1}{2n}$ (dễ thấy số tiền trong túi này vẫn nhỏ hơn 1) Giả sử tất cả các túi có số tiền đều lớn hơn $1-\frac{1}{2n}$ mà vẫn còn tiền chưa được cho vào túi, khi đó tổng số tiền sẽ lớn hơn $n(1-\frac{1}{2n})=n-\frac{1}{2}$ (vô lý) Như vậy tất cả tiền đều đã được chia vào túi và mỗi túi đều có số tiền không quá 1 Bài toán được chứng minh xong |
10-07-2014, 07:35 PM | #4 |
+Thành Viên Danh Dự+ Tham gia ngày: Oct 2012 Đến từ: THPT chuyên Lê Quý Đôn-Nha Trang-Khánh Hòa Bài gởi: 539 Thanks: 292 Thanked 365 Times in 217 Posts | Em nghĩ bài này còn có thể giải theo ý tưởng sau: $99+\frac{1}{2}=1+1+\cdots +1+\frac{1}{2}$(có $99$ số $1$). Mà ta có: $1=\frac{1}{n}+\frac{1}{n}+\cdots+\frac{1}{n}$ (có $n$ số $\frac{1}{n}$, $n \in \mathbb{N^*}$. Như vậy, số đồng xu trong bộ sưu tập có thể tăng đến số lượng tùy ý. Giả sử có $k (k>100)$ đồng xu trong bộ sưu tập này, khi đó, tồn tại một số số $t \ge 1$ sao cho $\frac{1}{t} \le \frac{100}{k}$. Ta sẽ chọn các số $t$ trên vào 1 nhóm và thêm một số số $m$ mà $\frac{1}{m} \ge \frac{100}{k}$ sao cho tổng các số $m$ và các số $t$ nhỏ hơn. Khi đấy, ta sẽ bỏ đi một số 1 trong phân tích $99+\frac{1}{2}=1+1+\cdots +1+ \frac{1}{2}$. Rồi tiếp tục áp dụng cách chia trên. __________________ i'll try my best. |
Bookmarks |
|
|