Có n học sinh tham gia một cuộc thi học sinh giỏi Toán và mỗi học sinh giải được đúng 3 bài toán. Hai học sinh bất kì có đúng một bài toán mà cả hai cùng giải được, trong khi đó mỗi bài toán được giải bởi đúng k học sinh. Tìm tất cả các số nguyên dương n và k thỏa mãn yêu cầu bài toán.
Tìm tất cả các số nguyên dương n và k thỏa mãn yêu cầu bài toán
#1
Đã gửi 20-06-2016 - 15:30
#2
Đã gửi 24-06-2016 - 18:56
Xét 1 người $A$ bất kì, người đó sẽ giải 3 bài toán bất kì, mỗi bài toán sẽ có $k$ người giải nó tính cả $A$. Vì mỗi người trong số $n$ người với $A$ có đúng 1 bài toán mà 2 người đều giải được nên trong 3 bài toán mà $A$ giải được thì không có người nào mà giải được ít nhất 2 trong số 3 bài. Nhưng mỗi người trong số $n-1$ người còn lại giải được ít nhất $1$ trong số $3$ bài toán đó nên tồn tại 1 song ánh giữa tập $n-1$ người đã trừ $A$ với tập các người giải được ít nhất $1$ bài toán trong số $3$ bài đã nêu trừ $A$. Vì vậy $n=3(k-1)+1$. Vì mỗi người giải được $3$ bài toán và mỗi bài toán được giải bởi $k$ người nên số bài toán được giải là $\frac{3n}{k}$, vì vậy $k$ là ước của $3n$ hay là ước của $9(k-1)+3$. Vì vậy $k$ là ước của $6$. Tuy nhiên nếu xét $k=6$ thì giả sử người $A$ làm được $3$ bài $1,2,3$ thì trong số $15$ người còn lại có $5$ người làm được bài $1$, $5$ người làm được bài $2$,$5$ người làm được bài $3$. Xét những người làm được bài $4$ thì theo nguyên lí Pigeonhole thì tồn tại $2$ người cùng làm được bài $4$, $2$ người cùng làm được bài $1$ hoặc $2$ hoặc $3$ (vô lí vì $2$ người bất kì thì chỉ làm được 1 bài chung). Vì vậy $(k;n)=(1;1);(2;4);(3:7)$
Bài viết đã được chỉnh sửa nội dung bởi JUV: 24-06-2016 - 20:09
0 người đang xem chủ đề
0 thành viên, 0 khách, 0 thành viên ẩn danh