Trang chủ » Những bài toán thú vị » Một bài Số học – Tổ hợp

Một bài Số học – Tổ hợp

Cho tập hợp X=\left \{ 1,2,...,50 \right \}. Tìm số nguyên dương nhỏ nhất k sao cho mọi tập con gồm k phần tử của X đều chứa hai phần tử phân biệt ab sao cho ab chia hết cho a+b

Lời giải: (Stranger0411 – VMF)

Chứng minh k \ge 39
Các cặp số thoả mãn ab chia hết a+b: (3;6);(4;12);(5;20);(6;12);(6;30);(7;42);(8;2);(9;18);(10;15);(10;40);(12;24);(12;36);(14;35);(15;30);(16;48);(18;36);(20;30);(21;28);(21;42);(24;40);(24;48);(30;45);(36;45)

Xét tập M=(6,12,15,18,20,21,24,35,40,42,45,48). Vì 23 cặp trên đều có phần tử thuộc M nên tập X \backslash M không thỏa mãn bài toán. Mà |X \backslash M|=38 \rightarrow k \ge 39

Chứng minh mọi tập có 39 phần tử đều thỏa mãn bài toán:
Xét tập A bất kì gồm 39 phần tử của X.
Chọn 12 cặp số trong 23 cặp trên sao cho các phần tử không trùng nhau: (3;6);(4;12);(5;20);(7;42);(8;2);(9;18);(10;15);(14;35);(18;36);(21;28);(24;40);(30;45)

Ta thấy rằng 12 cặp trên chứa 24 phần tử của X. Nên X chỉ còn lại 26 phần tử.
Vậy ít nhất 13 phần tử của A của phải thuộc 12 cặp trên. Theo nguyên lí Drichlet thì A chứa ít nhất một trong 12 cặp trên. Từ đó tập A thỏa mãn đề bài.

Q.E.D

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất /  Thay đổi )

Google photo

Bạn đang bình luận bằng tài khoản Google Đăng xuất /  Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất /  Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất /  Thay đổi )

Connecting to %s