Đến nội dung

Hình ảnh

Cho dãy số 1,2,3...2018. Có thể chọn được trong dãy số trên nhiều nhất bao nhiêu số để tổng hai số bất kì trong các số đã chọn chia hết cho 26

nguyên lí đi-rich-le

  • Please log in to reply
Chủ đề này có 3 trả lời

#1
Hagoromo

Hagoromo

    Hạ sĩ

  • Thành viên
  • 97 Bài viết

Cho dãy số 1,2,3...2018. Có thể chọn được trong dãy số trên nhiều nhất bao nhiêu số để tổng hai số bất kì trong các số đã chọn chia hết cho 26

Một lớp học có 34 học sinh có tổng số tuổi là 460.Có tồn tại 20 học sinh mà tổng số tuổi của họ lớn hơn 260 .Mọi người trả lời rõ ràng chi tiết hộ em nhé !


Bài viết đã được chỉnh sửa nội dung bởi Hagoromo: 21-08-2016 - 17:31


#2
12345678987654321123456789

12345678987654321123456789

    Trung sĩ

  • Thành viên
  • 187 Bài viết

Giả sử chọn được nhiều nhất trong dãy trên $n$ số : $a_1,a_2...a_n$

Ta có $\left\{\begin{matrix} a_1+a_2\equiv 0\;(mod\;26)\\ a_1+a_3\equiv 0\;(mod\;26) \end{matrix}\right.\Rightarrow 2a_1+a_2+a_3\equiv 0\;(mod\;26)$

Mà $a_2+a_3\equiv\;0(mod\;26)\Rightarrow 2a_1\equiv 0 (mod\;26)\Rightarrow \left[\begin{matrix} a_1\equiv0\;(mod\;26)\\ a_1\equiv13\;(mod\;26) \end{matrix}\right.$

Nếu $a_1\equiv0\;(mod\;26)$ thì $a_2\equiv0\;(mod\;26)$ do $a_1+a_2\equiv0\;(mod\;26)$. Tương tự, ta chứng minh được tất cả $n$ số $a_1,a_2...a_n$ đều chia hết cho $26$.

Nếu $a_1\equiv13\;(mod\;26)$ thì $a_2\equiv13\;(mod\;26)$ do $a_1+a_2\equiv0\;(mod\;26)$. Tương tự, ta chứng minh được tất cả $n$ số $a_1,a_2...a_n$ đều chia cho $26$ dư $13$.

Vậy ta sẽ phải chọn trong dãy nhiều nhất các số cùng chia hết cho $26$ hoặc cùng chia cho $26$ dư $13$.

Dễ dàng tính được trong dãy có $77$ số chia hết cho $26$ và $78$ số chia cho $26$ dư $13$.

Vậy chọn được trong dãy nhiều nhất $\boxed{78}$ số thỏa mãn đề bài.


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

Even when you had two eyes, you'd see only half the picture.


#3
12345678987654321123456789

12345678987654321123456789

    Trung sĩ

  • Thành viên
  • 187 Bài viết

Bài còn lại :

Chú ý : Cách này không được khuyên dùng trừ khi bạn đã hết cách :D Mình đang nghĩ cách khác tốt hơn

Bạn phải có một chút kiến thức về tổ hợp

 

Bài làm

Giả sử trái với điều phải chứng minh. Tức là không tồn tại $20$ học sinh có tổng số tuổi lớn hơn $260$ hay tổng số tuổi của $20$ học sinh bất kì trong lớp luôn không vượt quá $260$

Gọi số tuổi của các học sinh trong lớp lần lượt là $a_1,a_2,...a_{34}$. Ta có $a_1+a_2+...+a_{34}=460$

Theo giả sử ta có $a_{15}+a_{16}+...+a_{34}\leq260$

Mà $a_1+a_2+...+a_{34}=460$

Nên $a_1+a_2+...+a_{14}\geq460-260=200\;\boxed{1}$

Tương tự ta tạo được $C_{14}^{34}$ đánh giá giống như $\boxed{1}$ và bao gồm cả $\boxed{1}$

Cộng các đánh giá này vế theo vế ta được :

$C_{13}^{33}(a_1+a_2+...+a_{34})\geq 200.C_{14}^{34}\Leftrightarrow a_1+a_2+...+a_{34}\geq\frac{3400}{7}\approx 486> 460$ (Trái giả thiết)

Do đó ta có điều phải chứng minh.

 

Giải thích:

Bản chất của việc tạo ra các đánh giá giống như $\boxed{1}$ là để ta ghép đối xứng.

Ví dụ ta cần chứng minh $a+b+c>6$ ta có thể chứng minh $a+b>4$, $b+c>4$, $c+a>4$ rồi cộng theo vế được $2(a+b+c)>3.4\;\boxed{2}$ suy ra điều phải chứng minh.

Con số $C_{14}^{34}$ vai trò như số $3$ trong đánh giá $\boxed{2}$, là số đánh giá cần tạo lập.

Con số $C_{13}^{33}$ vai trò như số $2$ trong đánh giá $\boxed{2}$, là số lần xuất hiện của mỗi số $a_1,a_2...a_n$ trong đánh giá chốt.

 

Tính số đánh giá cần tạo lập : Ta thấy đánh giá tạo thành từ $14$ phần tử trong tập hợp gồm $34$ phần tử, vậy số đánh giá cần tạo lập là $C_{14}^{34}$

Tính số lần xuất hiện : Chính là tính số đánh giá có chứa một số trong dãy (chẳng hạn $a_1$). Hay nói cách khác là từ $a_1$ ta lập được bao nhiêu đánh giá khác nhau.

Giả sử trong dãy chỉ có $33$ phần tử $a_2,a_3...a_{34}$ và cần chọn $13$ phần tử bất kì trong dãy thì số cách chọn là $C_{13}^{33}$. Mỗi cách chọn này kết hợp với $a_1$ sẽ thành $14$ phần tử trong dãy $34$ phần tử ban đầu. Suy ra từ $a_1$ ta lập được $C_{13}^{33}$ đánh giá khác nhau.

Do đó số lần xuất hiện của mỗi số là $C_{13}^{33}$

 

Spoiler


Bài viết đã được chỉnh sửa nội dung bởi 12345678987654321123456789: 21-08-2016 - 22:09

Even when you had two eyes, you'd see only half the picture.


#4
redfox

redfox

    Trung sĩ

  • Thành viên
  • 100 Bài viết

Chọn $20$ người cao tuổi nhất. Gọi tổng số tuổi của họ là $S$

Người trẻ nhất trong $20$ người đó có tuổi không lớn hơn $\frac{S}{20}$.

Vậy tuổi của $14$ người còn lại không lớn hơn $\frac{S}{20}$. Vậy tổng số tuổi của $34$ người là $460$ không lớn hơn $\frac{14S}{20}+S=\frac{17S}{10}$. Vậy $S>260$, cách chọn thỏa mãn.






0 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh