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

[tcm]

Hi mọi người,

 

Mình đọc trong sách có 1 bài toán như sau: Cho các số tự nhiên từ 1 đến 2012. Hỏi có thể chọn ra nhiều nhất bao nhiêu số sao cho tổng của hai số bất kỳ trong chúng không chia hết cho hiệu của nó?

 

Còn đây là cách giải (của sách):
Nhận thấy, nếu hai số chia cho 3 cùng dư 2 thì hiệu của chúng chia hết cho 3, còn tổng của chúng chia cho 3 dư 1; nên tổng của chúng không chia hết cho hiện của chúng.
Trong các số tự nhiên từ 1 đến 2012, sẽ có 671 số chia cho 3 dư 2 là các số có dạng $3k + 2$ ($k = 0, 1, 2, ..., 670$). Khi đó hai số bất kỳ trong 671 số này có tổng chia 3 dư 1, hiệu chia hết cho 3, nên tổng không chia hết cho hiệu của chúng. Ta sẽ chứng minh rằng chọn được nhiều nhất là 671 số thỏa mãn điều kiện bài toán.
Thật vậy, nếu chọn 672 ( = 671 + 1) số trong các số từ 1 đến 2012, thì trong 672 số này luôn tìm được a, b (a > b) sao cho a - b $\leqslant$ 2 (Thật vậy, giả sử ngược lại thì hiệu giữa số nhỏ nhất và số lớn nhất trong các số đã chọn sẽ không nhỏ hơn 3.671 = 2013. Điều này mâu thuẫn với hiệu giữa số lớn nhất và số nhỏ nhất không vượt quá 2012 - 1 = 2011), nghĩa là a - b bằng 1 hoặc 2.
- Nếu a - b = 1 thì hiển nhiên a + b chia hết cho a - b ( = 1).
- Nếu a - b = 2 thì a + b là số chẵn nên a + b chia hết cho a - b ( = 2).
Như vậy từ 2012 số đã cho không thể chọn được hơn 671 số thỏa mãn điều kiện bài toán. Suy ra số lượng lớn nhất các số phải tìm là 671.

 

Mình thắc mắc đoạn đầu tiên là có nhất thiết phải đặt 2 số chia cho 3 cùng dư 2 hay không? Tại sao đề bài lại không đặt con số khác, ví dụ như chia cho 3 cùng dư 1 cũng được !?
Mình nghĩ là nếu chọn chia 2 dư 0 hoặc 1 thì hiển nhiên không được, nếu chọn chia 4 dư x hoặc chia 5 dư x ... thì khoảng cách giữa 2 số liên tiếp sẽ lớn, dẫn tới số lượng các số phải tìm ít đi, nên chọn chia 3 dư x sẽ là lựa chọn tốt nhất, phải không nhỉ?

 

Xin cảm ơn trước.

 

[tcm]

Please help me this problem !

[tcm]

Mọi người giúp mình giải đáp thắc mắc với ạ!

[IHateMath]

Good question, mình sẽ chỉ ra tại sao người ta lại đi đến lời giải đó.

Xét hai số nguyên dương $a,b$ bất kỳ, giả sử $a+b$ chia hết cho $a-b$. Khi đó, $a+b=(a-b)k$ với số nguyên dương $k$ nào đó. Biến đổi ta thu được:

$$\frac{a}{b}=\frac{k+1}{k-1}.$$

Nếu chọn $a=k+1, b=k-1$ thì đẳng thức trên được thỏa mãn với $k$ bất kỳ, nghĩa là nếu ta muốn chọn $n$ số sao cho điều kiện đề bài được thỏa mãn thì phải chọn sao cho hiệu của hai số liên tiếp phải lớn hơn $2$ (điều kiện cần). Khi đó ta nghĩ ngay tới việc chọn sao cho các số liên tiếp hơn kém nhau đúng $3$ (để được nhiều nhất -  cái này chính là tư tưởng tham lam). Vậy các số này có cùng số dư khi chia cho $3$. Ta thử xét các số đều chia hết cho $3$. Cách này được nhiều nhất là $670$ số (lấy tất cả các số chia hết cho $3$). Lại xét cách thứ hai: Tất cả chia $3$ dư $1$. Cách này thì được nhiều nhất là $671$ số, rõ ngon hơn cách một. Hay nếu xét cách thứ ba, chính là cách trong lời giải, thì cũng được nhiều nhất là $671$ số. Vậy cách trong lời giải không phải là duy nhất. 

Sau khi đã "chọn" được rồi, ta phải chứng minh là cách chọn của ta thỏa mãn đề bài (điều kiện đủ). Và đơn giản nhất là xét số dư cho $3$ (như trong lời giải).

Thoạt đầu, mình cũng không hiểu tại sao người ta lại nghĩ ra cách chọn như vậy. Nhưng ta phải lật ngược lại vấn đề: Chọn thế nào thì không được (bằng cách xét thử điều kiện hai số đề tổng chia hết cho hiệu), sau đó tìm cách chọn để không vướng vào điều kiện đó. Và lưu ý, phải "tham lam", chọn được nhiều nhất có thể, đối với những dạng thế này.

Bài viết đã được chỉnh sửa nội dung bởi IHateMath: 17-07-2017 - 16:54

[tcm]

Nếu chọn $a=k+1, b=k-1$ thì đẳng thức trên được thỏa mãn với $k$ bất kỳ

 

Vậy trong trường hợp $a \neq k + 1$ và $b \neq k - 1$ thì sao bạn?

 

Khúc tiếp theo, mình nghĩ việc chọn sao cho các số liên tiếp hơn kém nhau đúng $3$ đơn vị còn 1 lý do khác là nếu chọn con số lớn hơn (đặc biệt là số chẵn) thì có thể lúc này, $\frac{a}{b} = \frac{k + 1}{k - 1}$ đúng không nhỉ?

 

Còn khúc dưới ("xét các số chia hết cho 3") mình nghĩ là không cần thiết đúng không nhỉ? Vì khi đó có thể sẽ tồn tại 2 số sao cho tổng của chúng chia hết cho hiệu của chúng?

Bài viết đã được chỉnh sửa nội dung bởi tcm: 17-07-2017 - 22:39

[tcm]

Bạn gì ơi trả lời giúp mình thắc mắc trên với, sao trả lời được 1 lần rồi im luôn vậy.

Bài viết đã được chỉnh sửa nội dung bởi tcm: 20-07-2017 - 09:00

[IHateMath]

Vậy trong trường hợp $a \neq k + 1$ và $b \neq k - 1$ thì sao bạn?

 

Khúc tiếp theo, mình nghĩ việc chọn sao cho các số liên tiếp hơn kém nhau đúng $3$ đơn vị còn 1 lý do khác là nếu chọn con số lớn hơn (đặc biệt là số chẵn) thì có thể lúc này, $\frac{a}{b} = \frac{k + 1}{k - 1}$ đúng không nhỉ?

 

Còn khúc dưới ("xét các số chia hết cho 3") mình nghĩ là không cần thiết đúng không nhỉ? Vì khi đó có thể sẽ tồn tại 2 số sao cho tổng của chúng chia hết cho hiệu của chúng?

Xin lỗi bạn vì không trả lời mấy ngày qua.

Mình không cần quan tâm đến việc $a\ne k+1$ và $b\ne k-1$ làm gì. Mục đích của việc chọn là để tìm xem hiệu lớn nhất có thể của $a-b$ sao cho $a-b$ luôn chia hết $a+b$.

Chọn là $3$ chỉ đơn giản là vì $3$ là số nguyên nhỏ nhất mà lại lớn hơn $2$. Đúng là nếu chọn một số lớn hơn ba thì có khả năng như bạn nói (thực ra nếu chọn ba thì vẫn có đấy), nhưng đó không phải là lí do tại sao chọn $3$.

Phải xét chứ, vì biết đâu bạn loại đi những số đó đi rồi, số còn lại vẫn lớn hơn trong trường hợp dư $1$ hay $2$ thì sao?

[tcm]

Mục đích của việc chọn là để tìm xem hiệu lớn nhất có thể của $a-b$ sao cho $a-b$ luôn chia hết $a+b$.

 

Mình chưa hiểu lắm. Tại sao lại là $a - b$ chia hết cho $a + b$?

Bạn ghi là "Nếu chọn $a = k + 1$ và $b = k - 1$ ..." thì mình thắc mắc là trong trường hợp $a = (k + 1)x$ và $b = (k - 1)x$ với $x \in Z$ thì sẽ như thế nào ý?

 

Nếu chọn $3$ vẫn có khả năng xảy ra điều mình nói thì sao vẫn chọn thế bạn?

 

Còn câu cuối, mình chưa hiểu lắm, bạn có thể nói rõ hơn được không?

[IHateMath]

 

 

Mục đích của việc chọn là để tìm xem hiệu lớn nhất có thể của a−ba−b sao cho a−ba−b luôn chia hết a+ba+b.

Mình nói là "chia hết", không phải "chia hết cho". Thay vì nói "a chia hết cho b" người ta có thể nói "b chia hết a".

 

 

(...) mình thắc mắc là trong trường hợp a=(k+1)xa=(k+1)x và b=(k−1)xb=(k−1)x với x∈Zx∈Z thì sẽ như thế nào ý?

Trường hợp đó thật sự không có ý nghĩa trong việc tìm lời giải. Cho nên mình không xét tới nó

 

Nếu chọn 3

3vẫn có khả năng xảy ra điều mình nói thì sao vẫn chọn thế bạn?

Cái điều đó có thể xảy ra, nhưng không phải lúc nào cũng xảy ra. Bạn xem xem, nếu chọn toàn bộ chia $3$ dư $1$ hay $2$ nó đâu có xảy ra, nhưng nếu mình chọn toàn bộ chia hết cho $3$ thì có: $9=6+3$ chia hết cho $6-3=3$. 

 

Còn về cái cuối: Giả sử thế này đi, nếu chọn chia hết cho $3$ cả đi, và bạn chọn được $n$ số. Tuy nhiên trong số đó có những số làm cho điều kiện đề bài không được thỏa mãn. Vậy nếu vẫn giữ quyết định ban đầu thì bạn phải loại bớt đi ít nhất $k$ số chẳng hạn. Khi đó $n-k$ số còn lại thỏa mãn. Bây giờ nếu bạn chọn trường hợp khác (không chia hết cho ba) thì bạn chỉ chọn được nhiều nhất là $m$ số, và $m<n-k$ đi. Như vậy rõ ràng là bạn đâu thể nói rằng do xuất hiện một số số không thỏa đề bài mà kết luận rằng cách đó không thích hợp, phải đi vào xem xét cụ thể. Thực ra điều mình giả sử hồi nãy sai hoàn toàn (vì $n=670$ và $m=671$ ), nhưng đấy là khi đã biết giá trị cụ thể của chúng rồi!

[tcm]

1. Mình nói là "chia hết", không phải "chia hết cho". Thay vì nói "a chia hết cho b" người ta có thể nói "b chia hết a".

2. Trường hợp đó thật sự không có ý nghĩa trong việc tìm lời giải. Cho nên mình không xét tới nó

3. Cái điều đó có thể xảy ra, nhưng không phải lúc nào cũng xảy ra. Bạn xem xem, nếu chọn toàn bộ chia $3$ dư $1$ hay $2$ nó đâu có xảy ra, nhưng nếu mình chọn toàn bộ chia hết cho $3$ thì có: $9=6+3$ chia hết cho $6-3=3$. 

 

1. À, nó có phải giống như "b là ước của a" không? Kí hiệu: $b \ | \ a$ ?

2. Vậy nếu bài toán mà xét các trường hợp, trường hợp nào không liên quan thì bỏ qua hả bạn?

3. Cũng như câu hỏi trên, những trường hợp mà ta xét trong bài toán "có thể xảy ra" thì vẫn lấy làm lập luận được hả bạn?