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

[anhminh]

Cho tập A={1,2,...,50}
Tìm số k nhỏ nhất sao cho trong 1 tập con k phtử của A luôn tồn tại a,b thỏa mãn:
a^2 +b^2 là số chính phương.
Bài này chẳng khác gì bài thi của Trung Quócc hồi trước cả!Nhưng các bạn có muốn nói gì về nó không?

[gauxu]

Nếu mình không giải sai, thì trong 50 số đó có 12 cặp số thỏa mãn vậy thì có 26 số không thỏa , để đạt yêu cầu đề thì ta cần lấy ít nhất 13 số trong 24 số thỏa . Do đó k=39 là kết quả mình tìm được .

[anhminh]

Uh!
Nhưng mình muốn biết:
-LÀM SAO MÀ BẠN TÌM RA ĐƯỢC 12 CẶP QUAN TRỌNG ĐÓ?
-LÀM SAO MÀ BẠN TÌM RA ĐƯỢC TẬP HỢP 39 PHẦN TỬ THỎA MÃN GT?
Mình xin chia sẻ: Mình tìm ra chúng bằng GRAPH.Và bài toán trên đây liên quan dến bài toán lựa chọn tối ưu.

[gauxu]

Mình hơi dốt nên chỉ biết xét bằng bộ số Pythagore thôi tức là a=3k , b=4k với k N , từ đó suy ra 4k<50 k 12 .
Từ đó có được 12 cặp thỏa .
Vậy sẽ có 26 số không thỏa , giả sử tất cả đều cùng nằm trong một tập con của tập cho ban đầu , vậy phải tìm một lựa chọn tối ưu để luôn có được hai số thỏa mãn yêu cầu đề trong tập con đó , cách chọn ra 13 số thỏa , vậy thì với 1 tập có 39=26+13 số sẽ luôn tồn tại ít nhất 1 cặp số a, b sao cho a^2 + b^2 là 1 số chính phương.

[hoang]

Uh!
Nhưng mình muốn biết:
-LÀM SAO MÀ BẠN TÌM RA ĐƯỢC 12 CẶP QUAN TRỌNG ĐÓ?
-LÀM SAO MÀ BẠN TÌM RA ĐƯỢC TẬP HỢP 39 PHẦN TỬ THỎA MÃN GT?
Mình xin chia sẻ: Mình tìm ra chúng bằng GRAPH.Và bài toán trên đây liên quan dến bài toán lựa chọn tối ưu.

Dung vong lap for() la tim ra ngay ay ma

[chuyentoan]

Dùng vòng lặp FOR() !!!
Nhưng đi thi thì máy tính bỏ túi còn không cho đem nữa là computer

[anhminh]

[quote name='gauxu' date='Jul 11 2005, 08:29 PM']Mình hơi dốt nên chỉ biết xét bằng bộ số Pythagore thôi tức là a=3k , b=4k với k N , từ đó suy ra 4k<50    k 12 .
Từ đó có được 12 cặp thỏa .
Vậy sẽ có 26 số không thỏa , giả sử tất cả đều cùng nằm trong một tập con của tập cho ban đầu , vậy phải tìm một lựa chọn tối ưu để luôn có được hai số thỏa mãn yêu cầu đề trong tập con đó , cách chọn ra 13 số thỏa , vậy thì với 1 tập có 39=26+13 số sẽ luôn tồn tại ít nhất 1 cặp số a, b sao cho a^2 + b^2 là 1 số chính phương.[/quote]
[QUOTE]Hic!Mình không hiểu bạn đang nói gì cả!Xin lỗi nhé!Bạn có thể xem lại kĩ hơn được ko?
Đồng ý cao với chuyentoan,với lại bài toán của chúng ta hay thế này mà lại đưa tính toán vào thì thật là...
Hôm sau mình sẽ nói rõ hơn suy nghĩ của mình.
À! Mà đáp số là k=40 chứ!Chỉ tìm được 11 cặp PITAGO rời nhau thôi!

[chuyentoan]

chuyentoan nghĩ nên thực hiện theo các bước như sau:

B1: tìm tất cả các bộ Pitago nguyên thủy
B2: tìm tất cả các bộ Pitago (được suy ra từ bước 1)
B3: thiết lập đồ thì biểu diễn sự có chung phần tử giữa các bộ Pitago mà ta có (đồ thì này có thể liên thông hoặc gồm nhiều đồ thị rời nhau)
B4: Tìm tập đỉnh độc lập cực đại của đồ thị mà ta lâạ được. Số đỉnh trong tập đỉnh này chính là số bộ Pitago rời nhau nhiêu nhất.

Câu hỏi đặt ra là tại sao ta phải dùng đồ thị. Thực tế, nếu bác nào có "con mắt đại số" giỏi thì có lẽ từ các bộ Pitago nhận được cũng có thể tìm được số bộ độc lập. Nhưng nếu dùng đồ thị thì chúng ta sẽ bỏ qua được sự lằng nhằng của các con số, và các quan hệ được biểu diễn bằng hình học, mà rõ ràng các bạn có thể "dễ nhin hơn" khi nhìn vào các quan hệ giữa các bộ Pitago

[gauxu]

Bạn cứ nói suy nghĩ của bạn ra đi, để mình học hỏi, vì cách dùng Graph quả thật là mình chưa biết .
Kết quả của bạn là 40 , mình nghĩ là đúng vì mình đã có sai sót trong việc xét bộ số Pythagore, đúng là có 3 số trùng nhau là 12,24 và 36 , do đó chỉ còn lại 21 số chứa các cặp thỏa , và 29 số không chứa . Do đó chỉ cần lấy ra 11 số trong 21 số là sẽ có cặp thỏa mãn => k=29 + 11 =40 .

[anhminh]

Bác chuyentoan nói hoàn toàn ĐÚNG!Có điều xin bổ xung là ta ko chỉ có tìm ra 11 cặp Pitago rời nhau đâu mà còn chỉ ra 1 tập hợp 39 phtử ko có t/c của bài toán nữa !
Mình chỉ muốn trao đổi kĩ hơn về THUẬT TOÁN TÌM CÁC ĐỈNH MÀ chuyentoan GỌI LÀ" ĐỘC LẬP CỰC ĐẠI "(ý nghĩa cũng đúng nốt)ẤY!
Đó lại là 1 vấn đề thuộc về GRAPH ,đúng ko nào?
Mong các bạn tiếp tục suy nghĩ!

[anhminh]

Bây giờ ta hãy đặt vấn đề:
GIÁ NHƯ KHÔNG THỂ TÌM RA ĐƯỢC 11 CẶP PITAGO RỜI NHAU THÌ SAO?
để cho nó cụ thể hơn:bài toán rất dễ sau đây:
Tập X={1,2,...,35}
Tìm min k sao cho mọi tập con k phtử của X đều chứa 3 số a,b,c mà :abc=210.
(đừng quan tâm lắm đến bài toán cụ thể này mà hãy suy nghĩ câu hỏi đằng trên)