[VMO 2013] Bài 4 - Tổ hợp

[n.v.thanh]

[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[hakudoshi]

Cho trước một số số tự nhiên được viết trên một đường thẳng. Ta thực hiện các bước điền số lên đường thẳng như sau: tại mỗi bước, trước tiên xác định tất cả các cặp số kề nhau hiện có trên đường thẳng theo thứ tự từ trái qua phải, sau đó điền vào giữa mỗi cặp một số bẳng tổng của hai số thuộc cặp đó. Hỏi sau $2013$ bước, số $2013$ xuất hiện bao nhiêu lần trên đường thẳng trong các trường hợp sau:
a) Các số cho trước là: $1$ và $1000$?
b) Các số cho trước là: $1,2,...,1000$ và được xếp theo thức tự tăng dần từ trái qua phải?
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[kirin]

Đa 3 phải ko mn
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[TNP]

Làm lại câu a) (mất 2 tiếng đồng hồ, kiểu này sao thi hả trời )
Bây giờ, ta gán mỗi giá trị trên đường thẳng lên bảng, lấy $a(1,0)=1, a(2,0)=1000$, ta có được:
$a(p,q)=a(2p-1,q+1)$ và từ đó suy ra công thức $a(2m,q)=a(2m-1,q)+a(2m+1,q)$
Mặt khác, gọi một số là số mới nếu số đó được sinh ra tại bước đó và không xuất hiện trước đó, ta thấy rằng số mới luôn có giá trị cột là một số chẵn
Tại bước $i$, ta có $a(2,i)=1000+i$
Dễ thấy $a(2m,q)-a(2,q)=a(2m+1,q)-a(1,q) \Leftrightarrow a(2m,q)=a(2m+1,q)+1000+i-1=2013$
Tính từ từ là có được kết quả mà các anh chị đã tính ra
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[kirin]

Bước8, bước 1012, 1013 xuất hiện
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[innocent]

Có phải chỉ tính bước thứ 2013 đâu, là sau 2013 bước, có bao nhiêu bước làm xuất hiện số 2013 thì đếm đó chứ
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[Fool's theorem]

Mình làm ra kết quả là xuất hiện 2 lần trong tất cả các bước có bạn nào giống mình ko
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[cqb]

Bài này mình làm đc 2 lần: sau b8 và sau bước1013
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[BlaMaster]

Mình 2 lần nè, vẫn đang không biết sao bạn ở trên ra 3.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[huynhcongbang]

Nguyên văn bởi hakudoshi

Cho trước một số số tự nhiên được viết trên một đường thẳng. Ta thực hiện các bước điền số lên đường thẳng như sau: tại mỗi bước, trước tiên xác định tất cả các cặp số kề nhau hiện có trên đường thẳng theo thứ tự từ trái qua phải, sau đó điền vào giữa mỗi cặp một số bẳng tổng của hai số thuộc cặp đó. Hỏi sau $2013$ bước, số $2013$ xuất hiện bao nhiêu lần trên đường thẳng trong các trường hợp sau:
a) Các số cho trước là: $1$ và $1000$?
b) Các số cho trước là: $1,2,...,1000$ và được xếp theo thức tự tăng dần từ trái qua phải?

Câu a chỉ cần liệt kê ra là thấy ngay. Chú ý rằng ta chỉ quan tâm đến số lần xuất hiện của 2013 nên khi có 2 số đứng kề nhau mà tổng các số đều lớn hơn 2013 thì ta không cần liệt kê nữa.
Ta có
1 1000
B1: 1 1001 1000
B2: 1 1002 1001 2001 1000
B3: 1 1003 1002 2003 1001 3002 2001 3001 1000
B4: 1 1004 1003 2005 1002 (ta giữ lại 3 số đầu)
B5: 1 1005 1004 ...
B6: 1 1006 1005 2009 1004
B7: 1 1007 1006 2011 1005...
B8: 1 1008 1007 2013 1006...

Số 2013 xuất hiện lần đầu tiên. Sau đó, trừ tổng của cặp đầu tiên còn bé hơn 2013 thì các cặp còn lại đều lớn hơn 2013. Dễ thấy ngay từ đầu, số thứ 2 trong dãy tăng đúng 1 đơn vị nên sau 2013 bước thì số thứ 2 đó sẽ nhận giá trị 2013 đúng một lần.

Vậy số 2013 xuất hiện đúng 2 lần.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[Brandnewworld]

B8: 1 1008 1007 2013...
...
B1013: 1 2013 2012...
B1014: 1 2014 2013...
so 2013 xuat hien 3 lan chu
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[Fool's theorem]

Nói như bạn thì bước nào từ bước 8 trở đi chả có số 2013 xuất hiện vì nó có bị mất đi đâu
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[BlaMaster]

Bạn này, số 2013 xuất hiện ở bước 1013; còn cái ờ bước 1014 là số 2013 cũ ờ trên mà
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[huynhcongbang]

Nguyên văn bởi Brandnewworld

B8: 1 1008 1007 2013...
...
B1013: 1 2013 2012...
B1014: 1 2014 2013...
so 2013 xuat hien 3 lan chu

Bạn chú ý rằng đề hỏi là sau khi thực hiện 2013 bước thì nhận được bao nhiêu số 2013 trên đường thẳng. Chúng ta thấy là sau B8 thì có 1 số, B 1003 thì có thêm 1 số nữa và từ đó trở đi không còn thêm số 2013 nào khác nữa nên chỉ có 2 số như vậy thôi.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[TNP]

Nguyên văn bởi TNP

Làm lại câu a) (mất 2 tiếng đồng hồ, kiểu này sao thi hả trời )
Bây giờ, ta gán mỗi giá trị trên đường thẳng lên bảng, lấy $a(1,0)=1, a(2,0)=1000$, ta có được:
$a(p,q)=a(2p-1,q+1)$ và từ đó suy ra công thức $a(2m,q)=a(2m-1,q)+a(2m+1,q)$
Mặt khác, gọi một số là số mới nếu số đó được sinh ra tại bước đó và không xuất hiện trước đó, ta thấy rằng số mới luôn có giá trị cột là một số chẵn
Tại bước $i$, ta có $a(2,i)=1000+i$
Dễ thấy $a(2m,q)-a(2,q)=a(2m+1,q)-a(1,q) \Leftrightarrow a(2m,q)=a(2m+1,q)+1000+i-1=2013$
Tính từ từ là có được kết quả mà các anh chị đã tính ra

Em xin làm thử tiếp câu b)
Làm tương tự như trên, giả sử tồn tại một ô số $a(2m,q)$ mà nó bằng 2013, thì ta có
$a(2m,q)=a(2m+1,q)+a(2m-1,q)$
$a(L)+q=3012$ ($a(L,q)$ là ô ngay trước ô cuối cùng ở hàng $q$)
Mặt khác, vì ô liền trước ô cuối cùng(tức là ô $a(L,q)$) luôn là số mới, vậy nên ta có $a(L,q)=a(L-1,q)+1000$
Ta phải đi tính ô gần cúng cuồi này, gọi ô đó là $L_q$.
Ta có hệ thức truy hồi:$L_q=L_{q-1}+1000, L_1=999$
Ta sẽ tính được ô đó(em không biết xử lí dãy số, các anh làm tiếp phần này hộ em)
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]