Một bài toán thú vị

Con trai của một người bạn gửi một bài toán rất thú vị:

Có 2013 con bài. Trên mỗi con bài người ta viết 1 số bất kỳ. Tất cả 2013 số này khác nhau. Người ta úp các con bài xuống. 1 bước đi cho phép người chơi chỉ ra 10 quân bài và sẽ được thông báo 1 trong các số được viết trên các con bài này (không biết vị trí số đó). Tìm số t lớn nhất để đảm bảo tìm được t con bài mà có thể biết được số nào được viết trên từng con bài đó.

Chủ đề : Combinatorics and tagged , . Bookmark the permalink. Trackbacks are closed, but you can post a comment.

6 Comments

  1. Minh Ngọc Lê
    Posted 15/12/2013 at 6:37 pm | Permalink

    Một giới hạn trên cho số t là 2003. Nếu câu trả lời được luôn được chọn bằng số lớn nhất trong 10 số được chọn thì 9 số nhỏ nhất sẽ không bao giờ xuất hiện trong câu trả lời nào và số nhỏ nhất thứ 10 sẽ chỉ xuất hiện khi người chơi chọn cả 10 số. Như thế không thể có đủ dữ kiện để đoán ra 10 quân bài này.

  2. doanmo
    Posted 19/01/2014 at 6:02 pm | Permalink

    A guess: t = 18. I am trying to find a better value.

    • doanmo
      Posted 19/01/2014 at 6:14 pm | Permalink

      sorry, my guess is: t = 1905.

  3. Ngoc
    Posted 15/02/2014 at 5:25 am | Permalink

    Tác giả có thể đưa ra đáp án được không 🙂

  4. An Vinh
    Posted 20/02/2014 at 11:28 am | Permalink

    Tổng quát hóa bài toán, cho 10 là n, S là số quân bài ban đầu. Đặt s_n là số S lớn nhất sao cho “người thông báo” có cách để trả lời người chơi mà người chơi không thể xác định được số ở bất kì quân bài nào. Em đã chứng minh được là 3n-3 < s_n < n^2. (Theo đó, ở "bài toán thú vị", 1913 < t < 1986).
    Em dự đoán, s_n là số S lớn nhất sao cho "người thông báo" tìm được một tập A (nhiều hơn 1 phần tử) các hoán vị của S phần tử mà:
    i) Các "tuple" n phần tử bất kì cùng vị trí ở mỗi hoán vị cùng giao nhau.
    ii) Phần giao đó không chứa phần tử nào cùng vị trí ở tất cả các hoán vị trên.
    Thực tế, số 3n-3 được tìm ra bởi việc xét |A| = 2. Còn số n^2 thì khá hiển nhiên, vì cứ có n^2 quân bài là xác định được số ở một quân bài nào đó.

    • An Vinh
      Posted 28/02/2014 at 9:52 am | Permalink

      Em nhầm chút: s_n \ge 3n-3.
      Em đã giới hạn chặn trên xuống còn s_n < n^2-n+1. Từ đây dẫn tới s_3 = 6.

Post a Comment

Your email is never published nor shared. Required fields are marked *

You may use these HTML tags and attributes <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*
*