Chủ đề này có 8 trả lời

[hxthanh]

1. Đếm số cách chia $n$ cái kẹo (giống nhau) thành $3$ phần không tính đối xứng.

Các cách chia $(a,b,c)$ và $(c,b,a)$ được xem là như nhau. Các phần có thể rỗng!

2. Giả sử có 3 mệnh giá tiền là $1$ đồng, $2$ đồng và $4$ đồng. Tính số cách đổi $2n$ đồng ra các loại tiền mệnh giá trên.

[demon311]

Lâu không làm giờ làm bừa 1 câu xem thế nào

 

2) Với 2 đồng, ta có 2 cách 

Với 4 đồng, ta có 4 cách

Giả sử 2n đồng có 2n cách

Ta chứng minh với 2n+2 có 2n+2 cách
Thì từ 2n có 2n cách

Thêm 2 đồng thì có thêm 2 cách: thêm 2 tờ 1 đồng và 1 tờ 2 đồng 

Nên 2n+2 đồng có 2n+2 cách (dpcm)

[Nguyen Giap Phuong Duy]

Lâu không làm giờ làm bừa 1 câu xem thế nào

 

2) Với 2 đồng, ta có 2 cách 

Với 4 đồng, ta có 4 cách

Giả sử 2n đồng có 2n cách

Ta chứng minh với 2n+2 có 2n+2 cách
Thì từ 2n có 2n cách

Thêm 2 đồng thì có thêm 2 cách: thêm 2 tờ 1 đồng và 1 tờ 2 đồng 

Nên 2n+2 đồng có 2n+2 cách (dpcm)

Mình cảm nhận chắc sẽ đếm thiếu rất nhiều vì bạn hoàn toàn không dùng tới mệnh giá 4 đồng...

[TonnyMon97]

Bài một mình không nhầm là thế này. Mong mọi người góp ý.

Xét dãy số liên tiếp gồm n số 1 (ứng với n viên kẹo), ta ghi vào dãy số trên thêm 2 số 0 ở vị trí bất kì khi đó ta sẽ được "3 đoạn" (ứng với a;b;c). Rõ ràng phép đặt này là 1-1.

Vd: 111011011 <=> (3;2;2)

Theo tính chất của ánh xạ và qui tắc tổ hợp. Vậy số cách chia thỏa mãn đề bài là (n+2)C2

Bài viết đã được chỉnh sửa nội dung bởi TonnyMon97: 24-05-2015 - 22:12

[TonnyMon97]

 

 

Ta chứng minh với 2n+2 có 2n+2 cách
Thì từ 2n có 2n cách

Hình như bạn giải nhằm rồi, Thử n=3 cũng thấy thiếu 

[demon311]

Hình như bạn giải nhằm rồi, Thử n=3 cũng thấy thiếu 

 

n=3 => 2n=6

Có 6 cách mà:

 

6x1

4x1+1x2

2x1+2x2

3x2

2x1+1x4

1x2+1x4

 

Đủ mà

Hoặc nếu cần thì xét thêm cái 2n+4 có thêm 4 cách thì chắc là đủ

[hxthanh]

Không ngờ bài này sau khi được chọn làm PSW lại trở nên sôi nổi đến vậy. Tuy nhiên, chưa có một đáp án nào đúng cả! Cần phải nói thêm rằng: Câu 1 và Câu 2 dù sao thì cũng có một chút liên quan với nhau!
Đối với Câu 1 hay Câu 2, khi $n=4$ thì có $9$ cách, khi $n=5$ thì có $12$ cách. Các bạn hãy kiểm tra xem!

Chẳng hạn với $n=4$

 

Câu 1:

$\begin{array}{ccc} (4,0,0)&(0,4,0)&(1,3,0)\\ (1,0,3)&(0,1,3)&(2,2,0)\\ (2,0,2)&(2,1,1)&(1,2,1)\end{array}$

 

Câu 2:

Viết kết quả dưới dạng $abc=a.4+b.2+c$ (a tờ 4 đồng, b tờ 2 đồng, c tờ 1 đồng)

$\begin{array}{ccc} 008 & 016& 024 \\ 032 & 040 & 104 \\ 112 & 120 & 200 \end{array}$

Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 25-05-2015 - 07:15

[chanhquocnghiem]

1. Đếm số cách chia $n$ cái kẹo (giống nhau) thành $3$ phần không tính đối xứng.

Các cách chia $(a,b,c)$ và $(c,b,a)$ được xem là như nhau. Các phần có thể rỗng!

2. Giả sử có 3 mệnh giá tiền là $1$ đồng, $2$ đồng và $4$ đồng. Tính số cách đổi $2n$ đồng ra các loại tiền mệnh giá trên.

Câu $1$ :

Xét phương trình nghiệm nguyên không âm $x+y+z=n$ (*)

Số bộ ba số nguyên không âm $(a,b,c)$ (có phân biệt thứ tự) là nghiệm của (*) là $C_{n+2}^{2}$ (bộ)

Số bộ ba số nguyên không âm và cả 3 số bằng nhau là nghiệm của (*) là $M=\left \lfloor \frac{2n+1}{6} \right \rfloor-\left \lfloor \frac{2n-1}{6} \right \rfloor$

Số bộ ba số nguyên không âm (KHÔNG phân biệt thứ tự) có đúng 2 số bằng nhau là nghiệm của (*) là $N=\left \lfloor \frac{n+2}{2} \right \rfloor-\left \lfloor \frac{2n+1}{6} \right \rfloor+\left \lfloor \frac{2n-1}{6} \right \rfloor$

Số bộ ba số nguyên không âm (KHÔNG phân biệt thứ tự) khác nhau từng đôi một là nghiệm của (*) là $P=\frac{C_{n+2}^{2}-M-3N}{3!}=\frac{C_{n+2}^{2}-3(M+N)+2M}{6}=\frac{C_{n+2}^{2}-3\left \lfloor \frac{n+2}{2} \right \rfloor+2\left ( \left \lfloor \frac{2n+1}{6} \right \rfloor-\left \lfloor \frac{2n-1}{6} \right \rfloor \right )}{6}$

Với mỗi bộ ba bằng nhau, ta có $1$ cách chia thỏa mãn đề bài ; với mỗi bộ ba có đúng 2 số bằng nhau, ta có $2$ cách thỏa mãn đề bài ; với mỗi bộ ba gồm 3 số phân biệt, ta có $3$ cách chia thỏa mãn đề bài.

Vậy đáp án là $3P+2N+M=\frac{C_{n+2}^{2}+\left \lfloor \frac{n+2}{2} \right \rfloor}{2}$

 

Câu $2$ :

Gọi $i$ và $j$ lần lượt là số tờ tiền có mệnh giá là $4$ đồng và $2$ đồng ---> $i$ chạy từ $0$ đến $\left \lfloor \frac{n}{2} \right \rfloor$

+ Nếu $i=0$ ---> có $n+1$ cách vì $j$ có $n+1$ cách chọn ($j$ chạy từ $0$ đến $n$)

+ Nếu $i=1$ ---> có $n-1$ cách vì $j$ chạy từ $0$ đến $n-2$

.................................

.................................

+ Nếu $i=\left \lfloor \frac{n}{2} \right \rfloor$ ---> có $n+1-2\left \lfloor \frac{n}{2} \right \rfloor$ cách.

Vậy đáp án là $\sum_{i=0}^{\left \lfloor \frac{n}{2} \right \rfloor}(n+1-2i)=\left ( n+1 \right )\left \lfloor \frac{n+2}{2} \right \rfloor-2\sum_{i=0}^{\left \lfloor \frac{n}{2} \right \rfloor}i=(n+1)\left \lfloor \frac{n+2}{2} \right \rfloor-\left \lfloor \frac{n}{2} \right \rfloor\left \lfloor \frac{n+2}{2} \right \rfloor=\left \lfloor \frac{n+2}{2} \right \rfloor.\left \lfloor \frac{n+3}{2} \right \rfloor$

 

Hai đáp án của câu 1 và câu 2 là hoàn toàn đồng nhất (bằng nhau).Thật vậy :

+ Nếu $n$ chẵn thì $\left \lfloor \frac{n+2}{2} \right \rfloor.\left \lfloor \frac{n+3}{2} \right \rfloor=\left ( \frac{n+2}{2} \right )^2=\frac{(n+2)(n+1)+n+2}{4}=\frac{C_{n+2}^{2}+\left \lfloor \frac{n+2}{2} \right \rfloor}{2}$

+ Nếu $n$ lẻ thì $\left \lfloor \frac{n+2}{2} \right \rfloor.\left \lfloor \frac{n+3}{2} \right \rfloor=\frac{n+1}{2}.\frac{n+3}{2}=\frac{(n+2)(n+1)+n+1}{4}=\frac{C_{n+2}^{2}+\left \lfloor \frac{n+2}{2} \right \rfloor}{2}$

Vậy cả 2 câu có thể ghi đáp án là $\left \lfloor \frac{n+2}{2} \right \rfloor.\left \lfloor \frac{n+3}{2} \right \rfloor$

[hxthanh]

Như vậy là đã có câu trả lời đúng!

Sau đây là đáp án của "chương trình":

 

Câu 1.

Xét các bộ không âm $(a,b,c)$ với $a+b+c=n$ thỏa yêu cầu đề bài. Ta đếm theo vị trí trung tâm $b$

Ta có: $a+c=n-b\quad(1)$

Số nghiệm không âm của $(1)$ sao cho $a\le c$ là $\left\lfloor\frac{n-b+2}{2}\right\rfloor$

Ta chỉ cần đếm số nghiệm này vì nếu $a>c$ thì ta có bộ đối xứng $(c,b,a)$ ở đó $c<a$

Do đó, số cách chia thỏa mãn yêu cầu là

$$ S_n=\sum_{b=0}^n \left\lfloor\frac{n-b+2}{2}\right\rfloor=\sum_{b=2}^{n+2} \left\lfloor\frac{b}{2}\right\rfloor=\left\lfloor\frac{(n+2)^2}{4}\right\rfloor $$

Câu 2.

Gọi $a,b,c$ theo thứ tự là số tờ tiền $1$ đồng, $2$ đồng và $4$ đồng được quy đổi. Khi đó ta có phương trình:

$a+2b+4c=2n$

hay $\quad d+b+2c=n\quad(2)$ với $a=2d$ (số tờ $1$ đồng phải luôn là số chẵn)

Ta cũng đếm số nghiệm không âm của $(2)$ theo $b$

Ta có: $c=\frac{n-b-d}{2}\le \left\lfloor\frac{n-b}{2}\right\rfloor$

Như vậy ứng với mỗi $b$ giá trị của $c$ nhận từ $0,1,...,\left\lfloor\frac{n-b}{2}\right\rfloor$ tổng cộng $\left\lfloor\frac{n-b+2}{2}\right\rfloor$ giá trị. (còn lại $d=n-b-2c$) 

Do đó số nghiệm không âm của $(2)$ là

$$ S_n=\sum_{b=0}^n \left\lfloor\frac{n-b+2}{2}\right\rfloor=\sum_{b=2}^{n+2} \left\lfloor\frac{b}{2}\right\rfloor=\left\lfloor\frac{(n+2)^2}{4}\right\rfloor $$

 

Hai kết quả hoàn toàn giống nhau!

______________________________________

Ghi chú: Dãy số $u_n=\left\lfloor\frac{n^2}{4}\right\rfloor $

$\{u_n\}_{n\ge 0}: 0^2,0.1,1^2,1.2,2^2,2.3,3^2,3.4,4^2,4.5,...$

còn được biết đến với tên gọi: dãy "phần tư phương" (Quarter-squares) A002620