Đến nội dung


Chú ý

Nếu các bạn đăng kí thành viên mà không nhận được email kích hoạt thì hãy kiểm tra thùng thư rác (spam). Nếu không biết cách truy cập vào thùng thư rác thì các bạn chịu khó Google hoặc đăng câu hỏi vào mục Hướng dẫn - Trợ giúp để thành viên khác có thể hỗ trợ.


Hình ảnh

C/m: $max (n)\leq [k!e]-1$


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

#1 Hieutran2000

Hieutran2000

    Hạ sĩ

  • Thành viên
  • 54 Bài viết
  • Giới tính:Nam
  • Đến từ:THPT chuyên Lê Hồng Phong Nam Định

Đã gửi 10-06-2017 - 22:19

Phân hoạch tập $\left \{ 1,2,...n \right \}$ thành $k$ tập con ( có thể =$\varnothing$) sao cho: trong mỗi tập con không tồn tại 3 số mà có 1 số bằng tổng 2 số còn lại. Chứng minh: $max (n)\leq [k!e]-1$.


Bài viết đã được chỉnh sửa nội dung bởi Hieutran2000: 10-06-2017 - 22:20

$\sum =\prod$


#2 redfox

redfox

    Trung sĩ

  • Thành viên
  • 100 Bài viết
  • Giới tính:Nam
  • Đến từ:PTNK - ĐHQG TPHCM
  • Sở thích:wild animal, furry

Đã gửi 13-06-2017 - 14:21

Bổ đề: $\left \lceil \frac{\left \lfloor k!e \right \rfloor}{k} \right \rceil=\left \lfloor \left ( k-1 \right )!e \right \rfloor+1$ (có thể chứng minh nhờ công thức: $e=\sum_{k=1}^{\infty }\frac{1}{k!}$).

Ta định nghĩa: $A-B=\left \{ a-b|a\in A,b\in B,a>b \right \}$. Để ý rằng $A\subset C,B\subset D\Rightarrow A-B\subset C-D$.

Ta sẽ chứng minh nếu tập $N\subset \mathbb{Z}^+$ có tập con $M$ thỏa mãn $\left | M \right |\geq \left \lfloor k!e \right \rfloor,M-M\subset N$ thì không tồn tại cách phân hoạch thỏa mãn đề. Ta chứng minh bằng quy nạp theo $k$.

Với $k=1$, dễ dàng chứng minh bài toán đúng.

Giả sử $k-1$ đúng, xét phân hoạch $N$ thành $k$ tập hợp $A_1,A_2,...,A_k$. Theo Dirichlet, tồn tại $A_i$ sao cho $\left | A_i\cap M \right |\geq \left \lceil \frac{\left | M \right |}{k} \right \rceil\geq \left \lfloor \left ( k-1 \right )!e \right \rfloor+1$. Gọi $x$ là phần tử lớn nhất của $A_i\cap M$. Đặt $M'=\left \{ x \right \}-A_i\cap M$, ta có $\left | M' \right |\geq \left \lfloor \left ( k-1 \right )!e \right \rfloor$. Dễ thấy $M',M'-M'\subset A_i\cap M-A_i\cap M\subset M-M\subset N;M',M'-M'\subset A_i-A_i$

TH1: $M'\cap A_i\neq \varnothing$ hoặc $\left ( M'-M' \right )\cap A_i\neq \varnothing$, ta chọn được ba số trong $A_i$, một số bằng tổng hai số còn lại nên cách phân hoạch này không thỏa mãn.

TH2: $M',M'-M'\subset N'=N/A_i$, áp dụng bài toán với $k-1,N',M'$ với cách phân hoạch $N'$ thành $k-1$ tập hợp $A_1,A_2,...,A_k$ (trừ $A_i$), cách phân hoạch này không thỏa mãn với $N'$ nên cách phân hoạch $N$ thành $k$ tập hợp $A_1,A_2,...,A_k$ như trên cũng không thỏa mãn đề.

Áp dụng bài toán với $N=M=\left \{ 1,2,..,n \right \},n\geq \left \lfloor k!e \right \rfloor$ ta thấy không tồn tại cách phân hoạch thỏa mãn, vậy $n\leq \left \lfloor k!e \right \rfloor-1$.

(Q.E.D)


Bài viết đã được chỉnh sửa nội dung bởi redfox: 13-06-2017 - 14:26


#3 Donald Trump

Donald Trump

    Binh nhất

  • Thành viên mới
  • 29 Bài viết
  • Giới tính:Nam
  • Đến từ:White House
  • Sở thích:Làm nước Mỹ vĩ đại trở lại

Đã gửi 01-09-2017 - 09:19

Đây là định lý Schur, bạn có thể tham khảo cuốn Lý thuyết số sơ cấp của các số ( chương XII ).






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

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