Đến nội dung

Hình ảnh

Hãy tìm $m$ lớn nhất sao cho mỗi tập hợp đó đều chứa ít nhất 1 bộ số Pythagore

- - - - -

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

#1
gama

gama

    Binh nhất

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

Chia 100 số tự nhiên đầu tiên thành $m$ tập hợp. Hãy tìm $m$ lớn nhất sao cho mỗi tập hợp đó đều chứa ít nhất 1 bộ số Pythagore

DDTH


khong co gi kho chi co nhung gi chua biet ma thoi

#2
minhduc3001

minhduc3001

    Hạ sĩ

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

Giả sử $a,b,c$ là độ dài 3 cạnh của một tam giác vuông với $a$ là độ dài cạnh huyền. Theo định lý pitago ta có:

$a^{2}=b^{2}+c^{2}$. Nếu $b,c$ đồng thời không chia hết cho $3$ thì ta có: 

$b^{2};c^{2}\equiv 1(mod 3)$ suy ra $a^{2}\equiv 2(mod 3)$ (vô lí).

Vậy tồn tại ít nhất một trong hai số $b,c$ chia hết cho 3. Chứng minh tương tự ta suy ra được: Nếu $a,b,c$ là bộ ba số pitago thì tồn tại một trong ba số đó chia hết cho $3,4$ và $5$. Hay nói cách khác số đo các cạnh luôn có dạng: $a=5k;b=4k;c=3k$ với $k$ nguyên dương.(*)

(Thật vậy vì $b^{2}+c^{2}=k^{2}(3^{2}+4^{2})=k^{2}.5^{2}=a^{2}$).

Xét tập hợp $100$ số tự nhiên đầu tiên là $A=\left \{ 0;1;2;...;99 \right \}$ thì hiển nhiên $0$ không là độ dài cạnh của tam giác.

Theo nhận xét (*) thì tại $k=1$ ta có: $(a;b;c)=(5;4;3)$.

                                 tại $k=2$ ta có: $(a;b;c)=(10;8;6)$.

                                 ... 

                                 tại $k=19$ ta có: $(a;b;c)=(95;76;57)$.

 Với $k\geq 20 \Rightarrow a\geq 100$ không thuộ $A$. Vậy với $k$ chạy từ $1$ đến $19$ ta có $19$ cặp số pitago thuộc $A$.

 Xét tập hợp các phần tử còn lại của $A$ không thuộc các bộ số pitago trên là $B=\left \{ 1;2;7;11;13;14;... \right \}$ chia làm hai loại:

Loại 1: Nếu các phần tử của $B$ mà đồng thời không chia hết cho $3,4,5$ thì theo nhận xét (*) không thể là số đo một cạn của tam giác vuông.

Loại 2: Nếu các phần tử của $B$ ít nhất chia hết cho một trong các số $3,4,5$ thì khi đó $k\geq 20$ (loại).

Tóm lại từ $100$ số tự nhiên đầu tiên có thể chia thành nhiều nhất $19$ tập hợp con đều chứa ít nhất một bộ số pitago.

Vây $m= 19$.


  • LNH yêu thích

#3
LNH

LNH

    Bất Thế Tà Vương

  • Hiệp sỹ
  • 581 Bài viết

Giả sử $a,b,c$ là độ dài 3 cạnh của một tam giác vuông với $a$ là độ dài cạnh huyền. Theo định lý pitago ta có:

$a^{2}=b^{2}+c^{2}$. Nếu $b,c$ đồng thời không chia hết cho $3$ thì ta có: 

$b^{2};c^{2}\equiv 1(mod 3)$ suy ra $a^{2}\equiv 2(mod 3)$ (vô lí).

Vậy tồn tại ít nhất một trong hai số $b,c$ chia hết cho 3. Chứng minh tương tự ta suy ra được: Nếu $a,b,c$ là bộ ba số pitago thì tồn tại một trong ba số đó chia hết cho $3,4$ và $5$. Hay nói cách khác số đo các cạnh luôn có dạng: $a=5k;b=4k;c=3k$ với $k$ nguyên dương.(*)

(Thật vậy vì $b^{2}+c^{2}=k^{2}(3^{2}+4^{2})=k^{2}.5^{2}=a^{2}$).

Xét tập hợp $100$ số tự nhiên đầu tiên là $A=\left \{ 0;1;2;...;99 \right \}$ thì hiển nhiên $0$ không là độ dài cạnh của tam giác.

Theo nhận xét (*) thì tại $k=1$ ta có: $(a;b;c)=(5;4;3)$.

                                 tại $k=2$ ta có: $(a;b;c)=(10;8;6)$.

                                 ... 

                                 tại $k=19$ ta có: $(a;b;c)=(95;76;57)$.

 Với $k\geq 20 \Rightarrow a\geq 100$ không thuộ $A$. Vậy với $k$ chạy từ $1$ đến $19$ ta có $19$ cặp số pitago thuộc $A$.

 Xét tập hợp các phần tử còn lại của $A$ không thuộc các bộ số pitago trên là $B=\left \{ 1;2;7;11;13;14;... \right \}$ chia làm hai loại:

Loại 1: Nếu các phần tử của $B$ mà đồng thời không chia hết cho $3,4,5$ thì theo nhận xét (*) không thể là số đo một cạn của tam giác vuông.

Loại 2: Nếu các phần tử của $B$ ít nhất chia hết cho một trong các số $3,4,5$ thì khi đó $k\geq 20$ (loại).

Tóm lại từ $100$ số tự nhiên đầu tiên có thể chia thành nhiều nhất $19$ tập hợp con đều chứa ít nhất một bộ số pitago.

Vây $m= 19$.

Bạn cần phải chỉ ra cách phân hoạch tồn tại chứ, vả lại trong 19 bộ trên vẫn có một số bộ mà các số trùng nhau mà


Bài viết đã được chỉnh sửa nội dung bởi lenhathoang1998: 20-08-2013 - 16:58


#4
minhduc3001

minhduc3001

    Hạ sĩ

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

Bạn cần phải chỉ ra cách phân hoạch tồn tại chứ, vả lại trong 19 bộ trên vẫn có một số bộ trùng nhau mà

Em không hiểu lắm, anh co thể nói rõ hơn về cách phân hoạch tồn tại và tại sao trong 19 bộ trên có một số bộ trùng nhau không ạ.


Bài viết đã được chỉnh sửa nội dung bởi minhduc3001: 19-08-2013 - 22:45


#5
chanhquocnghiem

chanhquocnghiem

    Thiếu tá

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

$5$Chia 100 số tự nhiên đầu tiên thành $m$ tập hợp. Hãy tìm $m$ lớn nhất sao cho mỗi tập hợp đó đều chứa ít nhất 1 bộ số Pythagore

DDTH

Dễ dàng chứng minh được trong mỗi bộ ba số Pythagore phải có ít nhất $1$ số chia hết cho $5$.

Mà trong $100$ số tự nhiên đầu tiên (từ $0$ đến $99$) có $20$ bội của $5$.

Số $0$ không thể nằm trong một bộ ba Pythagore (gồm $3$ số khác nhau) nên $m$ không thể vượt quá $19$.

Tuy nhiên $m$ cũng không thể bằng $19$ như bạn minhduc3001 đã viết, bởi vì trong $19$ bộ ba mà bạn ấy kể ra có nhiều trường hợp có phần tử trùng nhau.

Ví dụ $(9;12;15)$ và $(12;16;20)$ có chung phẩn tử $12$ hoặc $(18;24;30)$ và $(24;32;40)$ có chung phần tử $24$ (không thỏa mãn yêu cầu bài toán)

 

Có thể lập được $50$ bộ ba số Pythagore mà trong mỗi bộ các phần tử đều nhỏ hơn $100$.

Trong $50$ bộ đó, có nhiều bộ có phần tử trùng nhau.

Dùng thuật toán Grant để chia các phần tử đó thành các bộ ba Pythagore không giao nhau sao cho số bộ ba là nhiều nhất.

Kết quả được $17$ bộ ba Pythagore không giao nhau là :

$( 3 ; 4 ; 5 )$ ; $( 6 ; 8 ; 10)$ ; $( 9;12;15)$ ; $(21;29;20)$ ; $( 7;24;25)$

$(16;34;30)$; $(84;91;35)$ ; $(28;53;45)$ ; $(14;48;50)$ ; $(33;44;55)$

$(11;61;60)$; $(39;52;65)$ ; $(42;56;70)$ ; $(18;82;80)$ ; $(51;68;85)$

$(54;72;90)$; $(57;76;95)$

(Các bội của $5$ được xếp ra sau cho dễ nhìn.Riêng số $75$ có mặt trong các bộ ba sau :

$(45;60;75);(40;75;85);(21;72;75)$

Hai bộ ba đầu bị loại vì mỗi bộ có đến $3$ bội của $5$.Bộ ba sau cùng cũng bị loại vì có phần tử $72$, nếu chấp nhận bộ ba này thì phải loại bộ ba $(54;72;90)$.

Trường hợp của số $40$ cũng tương tự)

 

Bây giờ ta lập ra $17$ tập hợp, mỗi tập hợp có chứa $3$ phần tử của mỗi bộ ba kể trên.Tiếp đó ta lấy $49$ phần tử còn lại (trong $100$ số tự nhiên đầu tiên) bổ sung một cách tùy ý vào $17$ tập hợp đó.Khi đó ta được $17$ tập hợp thỏa mãn ĐK bài toán.

Trả lời : Giá trị lớn nhất của $m$ là $17$.


Bài viết đã được chỉnh sửa nội dung bởi chanhquocnghiem: 02-10-2013 - 07:49

...

Ðêm nay tiễn đưa

Giây phút cuối vẫn còn tay ấm tay
Mai sẽ thấm cơn lạnh khi gió lay
Và những lúc mưa gọi thương nhớ đầy ...

 

http://www.wolframal...-15)(x^2-8x+12)





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

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