Đế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
* * * * * 3 Bình chọn

$\left \{ C_{2007}^i \right \}_{i=1}^{2007}$ có mấy số chẵn


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

#1 simon_1412

simon_1412

    Lính mới

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

Đã gửi 24-10-2007 - 12:13

Trong các số

$$C_{2007}^0, C_{2007}^1, C_{2007}^2,...,C_{2007}^{ 2007}$$

có bao nhiêu số chẵn?

 

Hãy tổng quát hóa bài toán



#2 nguyenta98

nguyenta98

    Thượng úy

  • Hiệp sỹ
  • 1259 Bài viết
  • Giới tính:Nam
  • Đến từ:THPT chuyên KHTN
  • Sở thích:Number theory, Combinatorics-number theory problems

Đã gửi 15-06-2013 - 10:58

Trong các số

$$C_{2007}^0, C_{2007}^1, C_{2007}^2,...,C_{2007}^{ 2007}$$

có bao nhiêu số chẵn?

 

Hãy tổng quát hóa bài toán

Giải như sau:

Quy ước kí hiệu $C_n^m=\binom{n}{m}$

Theo định lý Lucas ta có

$\binom{n}{m} \equiv \prod\binom{n_i}{m_i} \pmod{2}$

Với $n=n_k.2^k+n_{k-1}.2^{k-1}+...+n_1.2+n_0$ và $m=m_k.2^k+m_{k-1}.2^{k-1}+...+m_1.2+m_0$ 

Khi đó $\binom{n}{m} \vdots 2$ khi và chỉ khi tồn tại $\binom{n_i}{m_i} \vdots 2$ mà $\binom{n_i}{m_i} \in (\binom{1}{0},\binom{0}{1},\binom{1}{1},\binom{0}{0})$

Do đó $\binom{n_i}{m_i} \vdots 2$ khi và chỉ khi $n_i=0,m_i=1$ khi đó $\binom{0}{1}$ quy ước là $0$ và từ đó có hệ quả $\binom{n}{m}$ lẻ khi và chỉ khi với mọi $i=(1,2,...,k)$ thì $n_i\geq m_i$ $(1)$

Áp dụng vào bài toán $2007=2^{10}+2^9+2^8+2^7+2^6+2^4+2^2+2+1$

Theo hệ quả $(1)$ ta sẽ tính số số lẻ trong dãy $\binom{2007}{i}$

Khi đó đặt $i=a_{10}.2^{10}+a_9.2^9+a_8.2^8+...+a_1.2+a_0$ khi đó theo hệ quả $(1)$ $\binom{2007}{i}$ lẻ khi và chỉ khi $a_{10},a_{9},...,a_7,a_6,a_4,a_2,a_1,a_0\le 1$ và $a_5,a_3=0$

Do đó các số $a_{10},a_{9},...,a_7,a_6,a_4,a_2,a_1,a_0$ chỉ nhận một trong hai giá trị là $0,1$ nên số cách chọn là $2^9$

Do đó có $2^9$ số lẻ trong dãy trên như vậy có $2007+1-2^9=1496$ số chẵn

$$**********$$
Nhìn vào lời giải trên chắc chúng ta cũng tổng quát được

Tổng quát, cho dãy $\binom{n}{0},\binom{n}{1},...,\binom{n}{n}$ $(2)$
Và biểu diễn theo cơ số $2$ của $n$ là $a_k.2^k+a_{k-1}.2^{k-1}+...+a_1.2+a_0$ và trong các số $a_i$ có $p$ số là $1$

Khi đó số số lẻ trong $(2)$ là $2^p$ số, số số chẵn là $n+1-2^p$


Bài viết đã được chỉnh sửa nội dung bởi nguyenta98: 15-06-2013 - 10:58


#3 ilovelife

ilovelife

    Sĩ quan

  • Thành viên
  • 371 Bài viết
  • Giới tính:Nam
  • Đến từ:Đang ở ẩn

Đã gửi 15-06-2013 - 11:08

Trong các số

$$C_{2007}^0, C_{2007}^1, C_{2007}^2,...,C_{2007}^{ 2007}$$

có bao nhiêu số chẵn?

 

Hãy tổng quát hóa bài toán

Em tổng quát hóa + giải tổng quát luôn (thực ra bài này rất dễ):
Trong các số $C_{n}^0, C_{n}^1, C_{n}^2,\ldots,C_{n}^{n}$ (với $n \in \mathbb Z^+$)

Trong tam giác Pascal thì mỗi $C_{n}^0, C_{n}^1, C_{n}^2,\ldots,C_{n}^{ n}$ là các số ở hàng thứ $n$

hàng thứ $n$ thì luôn có $n+1$ số.

Do đó ta chỉ cần đếm số số chẵn trong mỗi hàng bằng cách đếm số số lẻ. Ta có cách làm sau:

 

Để đếm số số hạng lẻ trong cột $n$, chuyển $n$ qua hệ nhị phân. Goi $x$ là số chữ số một của $n_{(2)}$. Số số hạng lẻ sẽ là $2^x.$
 

 

Parity: To count odd terms in row $n$, convert n to binary. Let $x$ be the number of $1$s in the binary representation. Then number of odd terms will be $2^x$

-Wikipedia-

 

Chứng minh: Xem ở file đính kèm File gửi kèm  Odd Coefficients.pdf   56.15K   1906 Số lần tải (cái này em Google Search)

 

 

Áp dụng vào bài toán 

$2007 = 1024 + 512 + 256 + 128 + 64 + 16 + 4 + 2 + 1$

Nên có dạng nhị phân là $11111010111.$ ($9$ số $1$)

 

Vậy số số chẵn trong dãy mà đầu bài cho sẽ là: $\boxed{2007 +1 -  2^{9} = 1496}$
 
Nguyên nhanh tay quá :P


Bài viết đã được chỉnh sửa nội dung bởi ilovelife: 15-06-2013 - 11:15

God made the integers, all else is the work of man.

People should not be afraid of their goverment, goverment should be afraid of their people.

 


#4 nguyenta98

nguyenta98

    Thượng úy

  • Hiệp sỹ
  • 1259 Bài viết
  • Giới tính:Nam
  • Đến từ:THPT chuyên KHTN
  • Sở thích:Number theory, Combinatorics-number theory problems

Đã gửi 15-06-2013 - 11:15

 

Vậy số số chẵn trong dãy mà đầu bài cho sẽ là: $\boxed{2007  -  2^{9} = 1495}$

Bạn quên mất còn số $0$ là, phải là $2007+1-2^9=1496$ :D



#5 dark templar

dark templar

    Kael-Invoker

  • Hiệp sỹ
  • 3788 Bài viết
  • Giới tính:Nam
  • Đến từ:TPHCM
  • Sở thích:Đọc fanfiction và theo dõi DOTA chuyên nghiệp

Đã gửi 15-06-2013 - 12:06

1 bài toán cũng gần giống với bài trên:

 

Chứng minh rằng tồn tại vô số số nguyên dương $n$ sao cho các số $\binom{n}{0};\binom{n}{1};...;\binom{n}{n}$ đều là số lẻ.

 

Bài này được trích ra từ topic Số học-Tuyển tập các bài toán sưu tầm từ Mathlinks.ro-Bài toán 25.


"Do you still... believe in me ?" Sarah Kerrigan asked Jim Raynor - Starcraft II:Heart Of The Swarm.

#6 barcavodich

barcavodich

    Sĩ quan

  • Thành viên
  • 449 Bài viết
  • Giới tính:Không khai báo
  • Đến từ:Thái Bình---HSGS
  • Sở thích:Number Theory,Analysis

Đã gửi 16-06-2013 - 20:25

Nguyên nhanh quá 

Mình đang định làm :angry:


[topic2=''][/topic2]Music makes life more meaningful


#7 PSW

PSW

    Những bài toán trong tuần

  • Thành viên
  • 488 Bài viết
  • Giới tính:Nam

Đã gửi 02-07-2013 - 21:52

CHấm bài:

nguyenta98: 10 điểm

ilovelife: 5 điểm


1) Thể lệ
2) Danh sách các bài toán đã qua: 1-100, 101-200, 201-300, 301-400
Còn chờ gì nữa mà không tham gia!  :luoi:
 





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

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