Đến nội dung

Hình ảnh

bai toan ve quy nap

- - - - -

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

#1
phancuong123

phancuong123

    Binh nhất

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

chung minh mọi sô nguyen duong n, n$\geq$1 đều có thể viet dc duoi dang 4x + 5y=n( x, y$\in$ N)

 

 

 

 

 

 

 

 



#2
nguyencuong123

nguyencuong123

    Thiếu úy

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

Hình như $n\geq 12$

Nếu vậy: Mình làm như sau: xét n=12,x=3,y=0.đúng.

Giả sử n=k đúng nên $k=4x+5y$.

Ta sẽ chứng minh n=k+1 cũng đúng $k+1=4x+5y+1=4x-4+5y+5=4(x-1)+5(y+1)=4a+5b$. như vậy nên ta có đpcm


    :icon12:  :icon12:  :icon12:   Bình minh tắt nắng trời vương vấn :icon12:  :icon12:  :icon12:       

      :icon12: Một cõi chơi vơi, ta với ta  :icon12:       

:nav: My Facebook  :nav:  

 


#3
Kool LL

Kool LL

    Sĩ quan

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

Hình như $n\geq 12$

Nếu vậy: Mình làm như sau: xét n=12,x=3,y=0.đúng.

Giả sử n=k đúng nên $k=4x+5y$.

Ta sẽ chứng minh n=k+1 cũng đúng $k+1=4x+5y+1=4x-4+5y+5=4(x-1)+5(y+1)=4a+5b$. như vậy nên ta có đpcm

 

Xin lỗi trước, mình không có ý nói khích. Chỉ là bình luận để phát triển thêm. Cách giải của bạn không hoàn chỉnh, còn các thiếu sót sau :

1. Sao tìm được số 12 ? Nếu đổi đề bài khác thì lại mò số tiếp sao.

2. Quy nạp kiểu như bạn, có thể chon bước cơ sở là số $n_0$ nào cũng được, miễn sao $n_0$ đó biểu diễn được  dưới dạng $4x+5y=n$ (gọi tắt là BDD), rồi quy nạp thì cm được $\forall n\ge n_0$ thì $n$ đó đều BDD.

Chẳng hạn, lấy $n_0=0$ hoặc 4, hoặc 8 thì $\forall n_0\ge0$ đều BDD, hoặc $\forall n_0\ge4$ đều BDD, hoặc $\forall n_0\ge8$ đều BDD. Trong khi $n=1,2,3,6,7,11$ là các số không BDD.

3. Cũng có thể kiểm tra thử các số $n<12$, số lượng có hạn,không nhiều, thì dễ dàng kiểm tra. Nhưng nếu số lượng nhiều thì sao kiểm tra hết !?


Bài viết đã được chỉnh sửa nội dung bởi Kool LL: 01-09-2013 - 18:31


#4
Kool LL

Kool LL

    Sĩ quan

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

chung minh mọi sô nguyen duong n, n$\geq$1 đều có thể viet dc duoi dang 4x + 5y=n( x, y$\in$ N)

 

Không phải $\forall n\ge1$ đâu. $n=1,2,3,6,7,11$ thì không viết được.

 

Xin trình bày một cách giải như sau:

Giả sử số $n$ biểu diễn được dưới dạng $4x+5y=n$ (gọi tắt là BDD). Ta sẽ tìm $n$ có những điều kiện gì để ràng buộc.

Ta có :  $\forall y\in\mathbb{N}$ đều có dạng $y=4q+r$ với $q\in\mathbb{N}, r\in\{0,1,2,3\}$.

$\Rightarrow n=4x+5y=4(x+5q+r)+r=4k+r$ với $k\ge r, r\in{0,1,2,3,}$ thì $n$ đều BDD

$\Rightarrow$ các số $n$ không BDD thì có dạng $n=4k+r$ với $k<r, r\in{0,1,2,3}$. Chú ý $n \max\Leftrightarrow k,r \max$.

$\Rightarrow$ Số $n$ lớn nhất không BDD ứng với $r=3,k=r-1=2,n=4.2+3=11$.

Vậy $\forall n\ge12$ thì đều BDD. 

 

Nhận xét: Với cách giải này, ta cũng tìm được công thức cho tất cả các số BDD và các số không BDD. Ngoài ra có thể mở rộng cho bài toán tổng quát sau đây.


Bài viết đã được chỉnh sửa nội dung bởi Kool LL: 01-09-2013 - 20:46


#5
Kool LL

Kool LL

    Sĩ quan

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

Chung minh mọi sô nguyen duong n, n$\geq$12 đều có thể viet dc duoi dang 4x + 5y=n( x, y$\in$ N)

 

Mở rộng cho bài toán tổng quát sau đây :

"Cho $a,b\in\mathbb{Z}^+, (a,b)=1$. Tìm số tự nhiên $n$ lớn nhất mà không biểu diễn được dưới dạng $a.x+b.y=n$ với $x,y\in\mathbb{N}.$"

 

Ta  có bổ đề quen thuộc sau đây: "Với mọi $a,b\in\mathbb{Z}^+, (a,b)=1$ thì $\{b.0,b.1,...,b.(a-1)\}$ sẽ tạo thành một hệ thặng sư đầy đủ theo Modulo $a$. Tức là $\forall r'\in\{0,1,...,a-1\}, \exists r\in\{0,1,...,a-1\}$ sao cho $b.r\equiv r'\pmod{a}$".

 

Giả sử số $n$ biểu diễn được dưới dạng $ax+by=n$ với $x,y\in\mathbb{N}$. (Gọi tắt là BDD).

Không mất tính TQ, có thể g/s $b>a$. Ta có : $b=p.a+d$, $(p>0,0<d<a)$

$\forall y\in\mathbb{N},y=aq+r, q\in\mathbb{N},r\in\{0,1,...,a-1\}$

$\Rightarrow n=ax+by=ax+b(aq+r)=a(x+bq)+br=a(x+bq)+(pa+d)r=a(x+bq+pr)+dr$.

Do $0<d<a$ nên $(d,a)=1$. Theo bổ đề, ta có : $dr=a.q'+r'$; $q'=\left[\frac{dr}{a}\right]\in\{0,1,...,d-1\}$; $r'\in\{0,1,...,a-1\}$

$\Rightarrow n=a(x+bq+pr+q')+r'=ak+r'$ với $k\in\mathbb{N}, k\ge pr+q'=pr+\left[\frac{dr}{a}\right], r'=\left(r-a.\left[\frac{dr}{a}\right]\right)\in\{0,1,...,a-1\}$

Chú ý:

  • với $r_i\ne r_j\Leftrightarrow r'_i\ne r'_j$ và $r_i=r_j\Leftrightarrow r'_i=r'_j$.
  • với mỗi $r_i=i, (I\in\{0,1,...,a-1\}$, cho tương ứng một tập hữu hạn $n_i=ak+r'$ không BDD với $k<pr_i+q'_i$, số lớn nhất trong tập này là $n_{0_i}=a(pr_i+q_i'-1)+r_i'=a(pr_i-1)+dr_i=a(p.i-1)+di=(ap+d).i-a=b.i-a$.
  • $n_{0_i}$ đạt max $\Leftrightarrow r_i=i$ đạt max.

Vậy CTTQ cho số tự nhiên lớn nhất không BDD là $n_0=b.(a-1)-a=ab-a-b$.


Bài viết đã được chỉnh sửa nội dung bởi Kool LL: 02-09-2013 - 03:51





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

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