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

[Soulmaster]

Gọi S là tập hợp các số nguyên dương đồng thời thỏa mãn 2 đk sau:
1,Tồn tại 2 phần tử $x,y \in S$ sao cho $(x,y)=1$
2,Với bất kì $a,b\in S $thì $a+b \in S$.
Gọi T là tập hợp tất cacr các số nguyên dương ko phụ thuộc S.CM: rằng số phần tử của T hữu hạn và ko nhỏ hơn $\sqrt{s(T)}$, trong đó s(T) là tổng các phần tử của tập T(Nếu T=rỗng thì s(T)=0)

[tanlsth]

Dựa vào nhận xét phương trình $ax+by=n$ với $(a,b)=1$ có nghiệm nguyên dương với $n>ab$. Từ đó suy ra tập $T$ hữu hạn

Gọi $t_i$ là phần tử thứ $i$ thì ta chứng minh được $t_i \leq 2i-1$ suy ra điều phải chứng minh

[Mashimaru]

Anh tanlsth ơi, em thấy thực ra điều kiện để phương trình $ax+by=n$ với $(a,b)=1$ có nghiệm nguyên dương thì chỉ cần $n > ab - a -b$ thôi ạ, tức là mạnh hơn điều kiện anh đưa ra. Nhưng $t_i$ anh nói đến là gì ạ? Có phải là "phần tử lớn thứ $i$ của $T$" không ạ? Mà nếu là như thế thì làm sao chứng minh $t_i \leq 2i-1$ được ạ?

[phong than]

Giả sử $a_1<a_2<. . .<a_i$ là các phần tử của $T$, khi đó có $a_i-i$ số $x_1,x_2,. . .,x_{a_i-i}$ thuộc $S$ nhỏ hơn $a_i$.
Suy ra $a_i-x_j\in T$.
Suy ra $a_i-i\leq i-1$ hay là $a_i\leq 2i-1$.

[namdung]

Năm ngoái đọc đề Nghệ An, thấy mấy bài hay quá. Nhưng cũng đoán là ở đâu đó ra. Hôm trước đọc cuốn sách của Titu thì thấy quả thật là có bài này (Bài này gốc là đề đề nghị cho USA MO 2000).

Bài toán này liên quan đến định lý Sylvester khẳng định rằng N = ab - a - b là số nguyên lớn nhất không biểu diễn được dưới dạng ax + by với x, y nguyên không âm (ta gọi tắt là biểu diễn được). Ngoài ra, nếu p + q = N thì trong 2 số p, q, có đúng 1 số biểu diễn được. Như vậy ta biết được đích xác là |T| = (N+1)/2.

Trong diễn đàn "Seminar các PP toán sơ cấp" tôi có trình bày về bài toán Frobenius, tổng quát hóa bài toán trên. Tuy nhiên ngay cả TH n = 3 vẫn chưa có lời giải. Các bạn thử công phá xem sao?