|
|
|
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-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) |
Bookmarks |
|
|