Đến nội dung

Hình ảnh

$n \ge 2$ được gọi là tốt nếu với mọi $2 \le k \le n$ thì $n$ có dạng $n = a_1 + a_2 + \ldots + a_k$ trong đó $(n,a_k) = 1$

- - - - - @sohoc

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

#1
Minhcuc123

Minhcuc123

    Lính mới

  • Thành viên mới
  • 9 Bài viết

Một số nguyên dương $n \ge 2$ được gọi là tốt nếu với mọi $2 \le k \le n$ thì $n$ có dạng $n = a_1 + a_2 + \ldots + a_k$ trong đó $(n,a_k) = 1$ và các số $a_i$ là nguyên dương. Tính tổng tất cả các số tốt nhỏ hơn 2016 ($k$ là chỉ số) 

Giúp mình với mọi người


Bài viết đã được chỉnh sửa nội dung bởi perfectstrong: 16-09-2023 - 03:18
Tiêu đề & LaTeX


#2
Konstante

Konstante

    Trung sĩ

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

Nếu $2 \mid n$ thì $n$ không thể "tốt" do $2$ chắc chắn phải xuất hiện trong phân hoạch với $n-1$ phần tử. Ta sẽ chứng minh rằng nếu $n$ lẻ và $n \geq 3$ thì $n$ luôn là "tốt".

 

Xét quá trình phân hoạch như sau. Phân hoạch với $n$ phần tử là hiển nhiên vì $n = 2^0 + 2^0 + \dots + 2^0$. Để xây dựng phân hoạch với $n-1$ phần tử ta nhóm hai số $2^0$ để tạo thành số $2^1$.

 

Bằng cách nhóm các số có cùng lũy thừa $2^i$ (để tạo thành một số cũng là lũy thừa của $2$) như vậy ta sẽ xây dựng được các phân hoạch của $n$ với chiều dài từ $n$ cho đến $k$ trong đó $k$ là số các chữ số $1$ trong biểu diễn nhị phân của $n$, tức là $$n = 2^{i_1} + \dots + 2^{i_k}$$ với $0 \leq i_1 < i_2 < \dots < i_k$. Hiển nhiên là các phân hoạch này đều hợp lệ vì khi $n$ lẻ thì $(2^i, n) = 1$ với mọi $i$.

 

(Phần này có người khác giải quyết hộ mình)

Ta đi xây dựng các phân hoạch với chiều dài từ $2$ đến $k-1$. Phân hoạch với chiều dài $2$ là $n = (n-2^{i_k}) + 2^{i_k}$. Phân hoạch với chiều dài $3$ là $n = (n-2^{i_k}) + 2^{i_k-1} + 2^{i_k-1}$. Như vậy, bằng cách sử dụng đẳng thức $$2^{i_k} = 2^j + 2^j + 2^{j+1} + \dots + 2^{i_k-1}$$ta sẽ xây dựng được tất cả các phân hoạch có chiều dài từ $2$ đến $i_k$.

 

Do $0 \leq i_1 < i_2 < \dots < i_k$ nên $k \leq i_k$, tức là ta đã xây dựng được tất cả các phân hoạch để đảm bảo $n$ là "tốt".


Bài viết đã được chỉnh sửa nội dung bởi Konstante: 28-10-2023 - 16:13


#3
Minhcuc123

Minhcuc123

    Lính mới

  • Thành viên mới
  • 9 Bài viết

Nếu $2 \mid n$ thì $n$ không thể "tốt" do $2$ chắc chắn phải xuất hiện trong phân hoạch với $n-1$ phần tử. Ta sẽ chứng minh rằng nếu $n$ lẻ và $n \geq 3$ thì $n$ luôn là "tốt".

 

Xét quá trình phân hoạch như sau. Phân hoạch với $n$ phần tử là hiển nhiên vì $n = 2^0 + 2^0 + \dots + 2^0$. Để xây dựng phân hoạch với $n-1$ phần tử ta nhóm hai số $2^0$ để tạo thành số $2^1$.

 

Bằng cách nhóm các số có cùng lũy thừa $2^i$ (để tạo thành một số cũng là lũy thừa của $2$) như vậy ta sẽ xây dựng được các phân hoạch của $n$ với chiều dài từ $n$ cho đến $k$ trong đó $k$ là số các chữ số $1$ trong biểu diễn nhị phân của $n$, tức là $$n = 2^{i_1} + \dots + 2^{i_k}$$ với $0 \leq i_1 < i_2 < \dots < i_k$. Hiển nhiên là các phân hoạch này đều hợp lệ vì khi $n$ lẻ thì $(2^i, n) = 1$ với mọi $i$.

 

(Phần này có người khác giải quyết hộ mình)

Ta đi xây dựng các phân hoạch với chiều dài từ $2$ đến $k-1$. Phân hoạch với chiều dài $2$ là $n = (n-2^{i_k}) + 2^{i_k}$. Phân hoạch với chiều dài $3$ là $n = (n-2^{i_k}) + 2^{i_k-1} + 2^{i_k-1}$. Như vậy, bằng cách sử dụng đẳng thức $2^{i_k} = 2^j + 2^j + 2^{j+1} + \dots + 2^{i_k-1}$, ta sẽ xây dựng được tất cả các phân hoạch có chiều dài từ $2$ đến $i_k$.

 

Do $0 \leq i_1 < i_2 < \dots < i_k$ nên $k \leq i_k$, tức là ta đã xây dựng được tất cả các phân hoạch để đảm bảo $n$ là "tốt".

cảm ơn bạn







Được gắn nhãn với một hoặc nhiều trong số những từ khóa sau: @sohoc

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

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