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 > 2012

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-2012, 09:49 PM   #1
novae
Super Moderator
 
novae's Avatar
 
Tham gia ngày: Jul 2010
Đến từ: Event horizon
Bài gởi: 2,453
Thanks: 53
Thanked 3,057 Times in 1,288 Posts
[IMO 2012] Bài 3 - Tổ hợp

Trò chơi đoán kẻ nói dối là một trò chơi giữa hai người chơi $A$ và $B$. Quy tắc của trò chơi phụ thuộc vào hai số nguyên dương $k$ và $n$ mà cả hai người chơi đều đã biết trước.

Bắt đầu trò chơi, $A$ sẽ chọn các số nguyên $x$ và $N$ với $1 \le x \le N$. $A$ giữ bí mật số $x$ và nói số $N$ cho $B$. $B$ sẽ cố thu nhận thông tin về số $x$ bằng cách hỏi $A$ các câu hỏi như sau : mỗi câu hỏi bao gồm việc $B$ xác định một tập $S$ tùy ý các số nguyên dương (có thể là một tập đã được nhắc đến trong câu hỏi trước đó) và hỏi $A$ xem $x$ có thuộc $S$ hay không. Sau mỗi câu hỏi, $A$ phải trả lời hoặc không, nhưng có thể nói dối bao nhiêu lần tùy thích, chỉ có điều là phải trả lời đúng ít nhất một trong số $k+1$ câu hỏi liên tiếp.

Sau khi $B$ đã hỏi xong, $B$ phải chỉ ra một tập $X$ có tối đa $n$ số nguyên dương. Nếu $x \in X$, $B$ thắng; nếu ngược lại, $B$ thua. Chứng minh rằng :
  1. Nếu $n \ge 2^k$, $B$ có thể đảm bảo một chiến thắng.
  2. Với mọi $k$ đủ lớn, tồn tại một số nguyên $n \ge 1.99^k$ sao cho $B$ không thể đảm bảo có một chiến thắng.

[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________
M.

thay đổi nội dung bởi: novae, 11-07-2012 lúc 12:56 AM
novae is offline   Trả Lời Với Trích Dẫn
The Following 4 Users Say Thank You to novae For This Useful Post:
akaishuichi (11-07-2012), boykhtna1 (11-07-2012), philomath (11-07-2012), Shuichi Akai (11-07-2012)
Old 11-07-2012, 02:10 AM   #2
Shuichi Akai
+Thành Viên+
 
Tham gia ngày: Nov 2011
Bài gởi: 12
Thanks: 40
Thanked 10 Times in 8 Posts
Số câu hỏi B có thể đặt ra có giới hạn không ạ? hay là B có thể hỏi tuỳ ý bao nhiêu câu cũng được?
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
Shuichi Akai is offline   Trả Lời Với Trích Dẫn
Old 11-07-2012, 02:48 AM   #3
novae
Super Moderator
 
novae's Avatar
 
Tham gia ngày: Jul 2010
Đến từ: Event horizon
Bài gởi: 2,453
Thanks: 53
Thanked 3,057 Times in 1,288 Posts
Số câu hỏi là tùy ý nhé.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________
M.
novae is offline   Trả Lời Với Trích Dẫn
Old 11-07-2012, 07:04 AM   #4
Mashimaru
+Thành Viên+
 
Tham gia ngày: Mar 2008
Bài gởi: 89
Thanks: 19
Thanked 70 Times in 28 Posts
Mình xin làm thử bài đầu tiên Bài sau chưa có ý tưởng gì cả

Giả sử đã có $x \in S = \{1, ..., n\}$ với $n > 2^k$, ta chứng minh rằng sau một số câu hỏi, có thể tìm được tập con $S' \subset S$ sao cho $|S'| < |S|$ và chắc chắn $x \in S'$. Quá trình này sẽ dừng khi $|S| \leq 2^k$, và do đó suy ra được điều cần chứng minh.

Thật vậy, vì $|S| > 2^k$ nên tồn tại song ánh $f$ giữa một tập con thật sự $T$ của $S$ và tập hợp các chuỗi nhị phân độ dài $k$. Gọi $m$ là một phần tử nằm trong $S$ nhưng ko nằm trong $T$. Đồng thời ký hiệu $T_i$ là nghịch ảnh của tập hợp các chuỗi nhị phân có bit ở vị trí $i$-th là $0$, đối với $f$. Ta thực hiện các câu hỏi sau:

1. Hỏi liên tục các câu với tập hợp $\{m\}$. Nếu sau $k + 1$ câu hỏi như vậy mà ta đều nhận được đáp án "có" thì vì trong các câu này phải có ít nhất 1 câu $A$ nói thật nên có thể kết luận $X = \{m\}$, hết chuyện.

2. Ngược lại, giả sử tại câu hỏi thứ $i$-th ta có câu trả lời "không". Từ câu $i + 1$ đến câu $i + k$, ta lần lượt hỏi với các tập hợp $T_i$ như đã mô tả ở trên. Vì $i...i + k$ là $k + 1$ câu hỏi liên tiếp nên trong số chúng, có ít nhất 1 câu đáng tin. Thế tức là nếu ta kết hợp tất cả các điều kiện ngược với các câu trả lời thì dựa vào đó, tập hợp thu được sẽ vẫn chứa $x$. Ký hiệu $res(T_i) = T_i$ nếu câu trả lời ứng với câu hỏi $T_i$ là "có" và $res(T_i) = \overline{T_i}$ nếu câu trả lời này là "không" (ở đây $\overline{T_i}$ là tập hợp các chuỗi nhị phân độ dài $k$ và có bit ở vị trí $i$-th là $1$, hợp với các phần tử còn lại trong $S$, ngoài $m$ và các phần tử trong các $T_j$). Ta tìm giao của các tập hợp $\overline{res(T_i)} \cap (\bigcup T_i)$. Rõ ràng mỗi tập hợp kiểu này cho ta một mô tả về phần tử $x$ nằm trong giao của chúng (i.e. $x$ có bit thứ $i$-th là $0$ hay $1$). Vậy nên giao này khác rỗng (và tất nhiên là không phủ hết $(\bigcup T_i)$, vì bản thân các $\overline{res(T_i)}$ cũng không phủ được!). Do vậy, phần tử $x$ cần tìm mất đi ít nhất $1$ khả năng, và đó là điều ta đang muốn
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 

thay đổi nội dung bởi: Mashimaru, 11-07-2012 lúc 07:06 AM
Mashimaru is offline   Trả Lời Với Trích Dẫn
The Following 9 Users Say Thank You to Mashimaru For This Useful Post:
bboy114crew (12-07-2012), boykhtna1 (12-07-2012), Harry Potter (12-07-2012), huynhcongbang (12-07-2012), lexuanthang (11-07-2012), ngocson_dhsp (11-07-2012), nguoibimat (11-07-2012), perfectstrong (11-07-2012), philomath (11-07-2012)
Old 11-07-2012, 05:58 PM   #5
kien10a1
+Thành Viên+
 
kien10a1's Avatar
 
Tham gia ngày: Feb 2011
Đến từ: Vĩnh Yên- Vĩnh Phúc
Bài gởi: 371
Thanks: 43
Thanked 263 Times in 153 Posts
Gửi tin nhắn qua Yahoo chát tới kien10a1
Trích:
Nguyên văn bởi Mashimaru View Post
Mình xin làm thử bài đầu tiên Bài sau chưa có ý tưởng gì cả

Giả sử đã có $x \in S = \{1, ..., n\}$ với $n > 2^k$, ta chứng minh rằng sau một số câu hỏi, có thể tìm được tập con $S' \subset S$ sao cho $|S'| < |S|$ và chắc chắn $x \in S'$. Quá trình này sẽ dừng khi $|S| \leq 2^k$, và do đó suy ra được điều cần chứng minh.

Thật vậy, vì $|S| > 2^k$ nên tồn tại song ánh $f$ giữa một tập con thật sự $T$ của $S$ và tập hợp các chuỗi nhị phân độ dài $k$. Gọi $m$ là một phần tử nằm trong $S$ nhưng ko nằm trong $T$. Đồng thời ký hiệu $T_i$ là nghịch ảnh của tập hợp các chuỗi nhị phân có bit ở vị trí $i$-th là $0$, đối với $f$. Ta thực hiện các câu hỏi sau:

1. Hỏi liên tục các câu với tập hợp $\{m\}$. Nếu sau $k + 1$ câu hỏi như vậy mà ta đều nhận được đáp án "có" thì vì trong các câu này phải có ít nhất 1 câu $A$ nói thật nên có thể kết luận $X = \{m\}$, hết chuyện.

2. Ngược lại, giả sử tại câu hỏi thứ $i$-th ta có câu trả lời "không". Từ câu $i + 1$ đến câu $i + k$, ta lần lượt hỏi với các tập hợp $T_i$ như đã mô tả ở trên. Vì $i...i + k$ là $k + 1$ câu hỏi liên tiếp nên trong số chúng, có ít nhất 1 câu đáng tin. Thế tức là nếu ta kết hợp tất cả các điều kiện ngược với các câu trả lời thì dựa vào đó, tập hợp thu được sẽ vẫn chứa $x$. Ký hiệu $res(T_i) = T_i$ nếu câu trả lời ứng với câu hỏi $T_i$ là "có" và $res(T_i) = \overline{T_i}$ nếu câu trả lời này là "không" (ở đây $\overline{T_i}$ là tập hợp các chuỗi nhị phân độ dài $k$ và có bit ở vị trí $i$-th là $1$, hợp với các phần tử còn lại trong $S$, ngoài $m$ và các phần tử trong các $T_j$). Ta tìm giao của các tập hợp $\overline{res(T_i)} \cap (\bigcup T_i)$. Rõ ràng mỗi tập hợp kiểu này cho ta một mô tả về phần tử $x$ nằm trong giao của chúng (i.e. $x$ có bit thứ $i$-th là $0$ hay $1$). Vậy nên giao này khác rỗng (và tất nhiên là không phủ hết $(\bigcup T_i)$, vì bản thân các $\overline{res(T_i)}$ cũng không phủ được!). Do vậy, phần tử $x$ cần tìm mất đi ít nhất $1$ khả năng, và đó là điều ta đang muốn
Có một đoạn anh viết là $x $ thuộc giao của $\overline{res(T_i)} \cap (\bigcup T_i) $ nhưng nếu $x $ là $m $ thì nó không đúng mà anh.
Có lẽ ý anh là thế này, em thử diễn đạt lại. Ta thấy $x $ sẽ thuộc vào $\left \{ m \right \}\bigcup ResT_i $ và ta chỉ cần chứng minh $\bigcup ResT_i $ là con thực sự của $T $ thì sẽ khẳng định có một phần tử trong $T $ không phải là $x $, tương đương yêu cầu.
Giả sử $ResT_i $ với $i=1,2,...k $ bao gồm $T_{x_1},...T_{x_j} $ thì ta xét dãy nhị phân tại các vị trí $x_1,x_2,...,x_j $ có số $1 $, các vị trí còn lại là $0 $, sẽ được dãy này không là con của $\bigcup ResT_i $
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________
Quay về với nơi bắt đầu

thay đổi nội dung bởi: kien10a1, 11-07-2012 lúc 08:37 PM
kien10a1 is offline   Trả Lời Với Trích Dẫn
The Following User Says Thank You to kien10a1 For This Useful Post:
hoang_kkk (12-07-2012)
Old 11-07-2012, 08:02 PM   #6
hansongkyung
+Thành Viên+
 
hansongkyung's Avatar
 
Tham gia ngày: Jan 2012
Đến từ: Han Tae Woong - IMO 1998
Bài gởi: 493
Thanks: 109
Thanked 406 Times in 240 Posts
Gửi tin nhắn qua Yahoo chát tới hansongkyung
Phần a có thể làm bằng cách chỉ ra 1 trường hợp đúng không?
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________
Trương Mạnh Hùng, lớp 12A1, THPT Mai Sơn, Sơn La.
hansongkyung is offline   Trả Lời Với Trích Dẫn
Old 12-07-2012, 03:22 AM   #7
Mashimaru
+Thành Viên+
 
Tham gia ngày: Mar 2008
Bài gởi: 89
Thanks: 19
Thanked 70 Times in 28 Posts
@kien10a1: Ồ đoạn đó là anh ký hiệu dở đấy. Cái $x$ ở đây là thay cho 1 phần tử bất kỳ chứ ko phải là cái $x$ mình cần tìm Cảm ơn em
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
Mashimaru 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à 02:42 AM.


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