Trích:
Nguyên văn bởi huynhcongbang Có một bài thế này: Cho dãy hữu hạn có độ dài $n$ và các phần tử là 0 hoặc 1. Khoảng cách giữa hai dãy chính là số vị trí mà phần tử tương ứng ở hai dãy khác nhau. Xét $m$ dãy tùy ý và khoảng cách giữa hai dãy bất kỳ đều không vượt quá $d$. Chứng minh rằng $m\le \frac{2d}{2d-n}$. Bài này có thể giải bằng cách dùng double counting. Tuy nhiên, ở đây thú vị là $2d=n$ nên đánh giá ở trên trở thành vô ích vì $m \le + \infty$. Mời các bạn góp ý thêm. |
Em thấy bài 47 nó khá gần với bài toán này: "Chứng minh rằng không thể có nhiều hơn 4096 cây nhị phân độ dài 24 sao cho 2 cây bất kì trong chúng có ít nhất 8 vị trí khác nhau". Mò mẫm một hồi thì ra đáp án là $2^{n+1}$ nhưng vẫn chưa biết giải thích sao.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]