|
|
|
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-2012, 09:49 PM | #1 |
+Thành Viên Danh Dự+ 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 có 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 :
__________________ M. thay đổi nội dung bởi: novae, 11-07-2012 lúc 12:56 AM |
The Following 4 Users Say Thank You to novae For This Useful Post: |
11-07-2012, 02:10 AM | #2 |
+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? |
11-07-2012, 02:48 AM | #3 |
+Thành Viên Danh Dự+ 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é. __________________ M. |
11-07-2012, 07:04 AM | #4 |
+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 thay đổi nội dung bởi: Mashimaru, 11-07-2012 lúc 07:06 AM |
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) |
11-07-2012, 05:58 PM | #5 | |
+Thành Viên+ | Trích:
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 $ __________________ 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 | |
The Following User Says Thank You to kien10a1 For This Useful Post: | hoang_kkk (12-07-2012) |
11-07-2012, 08:02 PM | #6 |
+Thành Viên+ | Phần a có thể làm bằng cách chỉ ra 1 trường hợp đúng không? |
12-07-2012, 03:22 AM | #7 |
+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 |
Bookmarks |
|
|