Chủ đề này có 6 trả lời

[nucnt772]

BÀI TOÁN: Có 2000 học sinh tham gia 1 cuộc thi trắc nghiệm. Bài thi gồm 5 câu, mỗi câu có 4 cách trả lời khác nhau và mỗi học sinh phải chọn 1 trong 4 cách đó. Tìm số tự nhiên n bé nhất sao cho có 1 kiểu làm bài nào đó của các học sinh thỏa mãn: với n học sinh bất kỳ chọn ra, ta có thể tìm được trong nhóm n học sinh này 4 người mà bất cứ 2 người nào trong số 4 người đó cũng phải có ít nhất 2 câu trả lời khác nhau.

Bài viết đã được chỉnh sửa nội dung bởi nucnt772: 13-08-2012 - 21:47

[Karl Heinrich Marx]

Bài này đơn thuần là Dirichle, có tất cả $4^5$ cách làm. 2000 bạn thì ta có thể chia ra $4^5$ nhóm và mỗi nhóm nhiều nhất 2 bạn, từ đó suy ra nếu lấy 7 người thì ít nhất phải có 4 bạn ở 4 nhóm khác nhau, ở khác nhóm thì bài làm 2 bạn này khác nhau suy ra đpcm. Còn nếu n<7 thì ta thấy luôn chọn đc 3 nhóm mà mỗi nhóm có ít nhất 2 bạn làm bài giống nhau, chọn 3 nhóm này thì k thể tìm đc 4 bạn thỏa đề bài.

[The Gunner]

ở hai nhóm khác nhau thì chưa chắc đã có 2 đáp án khác nhau nên mình nghĩ kq trên chưa đúng Mặt khác nếu có trường hợp 2000 thí sinh làm cùng 1 đáp án hết thì sao nhỉ )

[Karl Heinrich Marx]

Đề bài là tồn tại 1 kiểu làm bài của các hs sao cho cứ lấy n người sẽ có 4 người làm đôi một khác nhau.

[The Gunner]

Đề bài là tồn tại 1 kiểu làm bài của các hs sao cho cứ lấy n người sẽ có 4 người làm đôi một khác nhau.

Bạn đọc kĩ lại vì là đôi một trong đó thì phải khác ít nhất 2 câu, ví dụ
Chọn ra 7 người mà họ là với đáp án như thế này thì ko tồn tại
1a--------------5a
1a--------------5b
1a---------------5c
1a---------------5d
1b---------------5a
1c---------------5a
1d---------------5a

ở dấu ------------ là các câu còn lại có đáp án giống nhau

[The Gunner]

Ý tưởng của mình như thế này ta xét 4 nhóm như sau $S_j=\left\lbrace{ x|\sum\limits_{i=1}^5{x_i} \equiv j (\mod 4)}\right\rbrace$ với $j=0,1,2,3$
Trong đó $x_i$ là tình trạng làm 5 bài của của thí sinh $x$ với $x_i \in \left\lbrace{ 1,2,3,4}\right\rbrace$
Do đó nếu $x \ne y$ và $x,y \in S_j$ thì nếu $ x_i \ne y_i$ thì $x_j \ne y_j$
Mà do theo trên thì có tối đa hai người làm bài giống nhau nên suy ra nếu trong một nhóm có ít nhất $7$ người thì sẽ tồn tại 4 người làm bài khác nhau cùng thuộc một nhóm. Do đó ta cần ít nhất $4.6+1=25$ người

Bài viết đã được chỉnh sửa nội dung bởi The Gunner: 17-08-2012 - 20:06

[Karl Heinrich Marx]

Ý tưởng của mình như thế này ta xét 4 nhóm như sau $S_j=\left\lbrace{ x|\sum\limits_{i=1}^5{x_i} \equiv j (\mod 4)}\right\rbrace$ với $j=0,1,2,3$
Trong đó $x_i$ là tình trạng làm 5 bài của của thí sinh $x$ với $x_i \in \left\lbrace{ 1,2,3,4}\right\rbrace$
Do đó nếu $x \ne y$ và $x,y \in S_j$ thì nếu $ x_i \ne y_i$ thì $x_j \ne y_j$
Mà do theo trên thì có tối đa hai người làm bài giống nhau nên suy ra nếu trong một nhóm có ít nhất $7$ người thì sẽ tồn tại 4 người làm bài khác nhau cùng thuộc một nhóm. Do đó ta cần ít nhất $4.6+1=25$ người

Uh mình sai vì không đọc có ít nhất 2 câu trả lời khác nhau, thực ra thì đơn giản thôi k cần đặt ra như thế cho phức tạp, rõ ràng nếu các bạn làm bài khác nhau thì nhiều nhất là 4 bạn làm giống 4 câu nên nếu lấy ra 13 bạn thì sẽ có 4 bạn làm khác 2 câu. Để lấy ra 13 người làm khác nhau thì cần 25 người.