Diễn Đàn MathScopeDiễn Đàn MathScope
  Diễn Đàn MathScope
Ghi Danh Hỏi/Ðáp Thành Viên Social Groups Lịch Ðánh Dấu Ðã Ðọc

Go Back   Diễn Đàn MathScope > Sơ Cấp > Việt Nam và IMO > 2014

News & Announcements

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é !

* Nội quy MathScope.Org

* Một số quy định chung !

* 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

* Những câu hỏi thường gặp

* Về việc viết bài trong Box Đại học và Sau đại học


Trả lời Gởi Ðề Tài Mới
 
Ðiều Chỉnh Xếp Bài
Old 09-07-2014, 08:44 PM   #1
Fool's theorem
+Thành Viên Danh Dự+
 
Fool's theorem's Avatar
 
Tham gia ngày: Oct 2012
Đến từ: T1 K46 Chuyên ĐHSP Hà Nội
Bài gởi: 187
Thanks: 42
Thanked 191 Times in 101 Posts
Gửi tin nhắn qua Yahoo chát tới Fool's theorem
[IMO 2014] Bài 5 - Tổ hợp



Nguồn: facebook thầy Lê Anh Vinh
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
Hình Kèm Theo
Kiểu File : png IMO-Bài 5.png (84.5 KB, 324 lần tải)
__________________
Hope against hope.

thay đổi nội dung bởi: Fool's theorem, 09-07-2014 lúc 08:46 PM
Fool's theorem is offline   Trả Lời Với Trích Dẫn
The Following User Says Thank You to Fool's theorem For This Useful Post:
thiendieu96 (10-07-2014)
Old 10-07-2014, 04:05 AM   #2
namdung
Administrator

 
Tham gia ngày: Feb 2009
Đến từ: Tp Hồ Chí Minh
Bài gởi: 1,341
Thanks: 209
Thanked 4,062 Times in 777 Posts
Gửi tin nhắn qua Yahoo chát tới namdung
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.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
namdung is offline   Trả Lời Với Trích Dẫn
The Following 4 Users Say Thank You to namdung For This Useful Post:
duykhanhht (01-08-2015), kimlinh (10-07-2014), lupanh7 (10-07-2014), osp (10-07-2014)
Old 10-07-2014, 10:50 AM   #3
lupanh7
+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
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
lupanh7 is offline   Trả Lời Với Trích Dẫn
Old 10-07-2014, 07:35 PM   #4
quocbaoct10
+Thành Viên Danh Dự+
 
quocbaoct10's Avatar
 
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 364 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.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________
i'll try my best.
quocbaoct10 is offline   Trả Lời Với Trích Dẫn
Trả lời Gởi Ðề Tài Mới

Bookmarks

Ðiều Chỉnh
Xếp Bài

Quuyền Hạn Của Bạn
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is Mở
Smilies đang Mở
[IMG] đang Mở
HTML đang Tắt

Chuyển đến


Múi giờ GMT. Hiện tại là 09:17 PM.


Powered by: vBulletin Copyright ©2000-2018, Jelsoft Enterprises Ltd.
Inactive Reminders By mathscope.org
[page compression: 54.00 k/60.19 k (10.28%)]