Bài toán về số "tốt"

1) (T11/461): Cho n số nguyên dương khác nhau. Mỗi cặp số được lấy từ n số nguyên dương đã cho được gọi là tốt nếu tỉ số giữa hai số này là 2 hoặc 3. Hỏi khi cho $n=m^2$ số nguyên dương khác nhau tuỳ ý thì số cặp số tốt lớn nhất bằng bao nhiêu ?

Lời giải

Đặt $a_i=2^r_i.3^s_i.t_i, (t_i,6)=1$

Ta thấy $(a_i,a_r)$ thoả đề bài khi $t_i=t_r$ do đó số cặp số tốt trong n số $a_i$ không vượt quá số cặp số tốt trong n số $2^r_i.3^s_i$ (i từ 1 đến n)

Cặp $(2^r_i.3^s_i,2^r_j.3^s_j)$ tốt khi và chỉ khi

$r_i=r_j$ và $|s_i-s_j|=1$ hoặc $s_i=s_j$ và $|r_i-r_j|=1$

Xét n điểm $A_i=(r_i, s_i)$ ( trong tạp chí ghi sai $"A_i=(r_i,r_j)"$)

Như vậy cặp cặp $(2^r_i.3^s_i,2^r_j.3^s_j)$ tốt khi và chỉ khi $A_iA_j=1$.

Giả sử n điểm $A_i$ nằm trên k đường thẳng song song với trục Ox kí hiệu là $d_1,..d_k$

Gọi $m_l$ là số điểm $A_i$ nằm trên $d_l$ (l=1,..k) và $d_h$ chưa nhiều điểm $A_i$ nhất, Khi đó

$n=\sum m_i \le k m_h$

2) Cho $m \ge 2$ là một số nguyên. Số n nguyên không âm gọi là m-tốt nếu mỗi a nguyên tố cùng nhau với n, có $n | (a^m-1)$. Chứng minh rằng mọi số m-tốt lớn nhất bằng $4m(2^m-1)$

Giải.

Nếu m lẻ thì $n | (n-1)^m-1$ tương đương $n|2$ (khai triển).

$m=2^t.q (t \ge 1)$, q lẻ. Đặt $n=2^u(2v+1)$. Giả sử n là m-tốt khi đó $(2v-1)^m-1 \equiv 2^m-1 (mod 2v+1)$ (*). Nếu chọn $a=2(2v+1)+1=4v+3$ thì

$n | (a^{q})^{2t}-1)$  mà $v_2 (a^{q})^{2t}-1)=t+2$ do $v2(a^q-1)=1, v_2(a^q+1)=2$ (không được)

Nên chọn $a=8v+5$ ta có $v2(n)=u$ nên $u \le t+2$ vì thế kết hợp với  ta có điều phải chứng minh.