[VMO 2014] Bài 3 - Tổ hợp

[huynhcongbang]

Bài 3.
Cho đa giác đều có 103 cạnh. Tô màu đỏ 79 đỉnh của đa giác và tô màu xanh các đỉnh còn lại. Gọi $A$ là số cặp đỉnh đỏ kề nhau và $B$ là số cặp đỉnh xanh kề nhau.
a. Tìm tất cả các giá trị có thể nhận được của cặp $(A,B).$
b. Xác định số cách tô màu các đỉnh của đa giác để $B=14.$ Biết rằng hai cách tô màu được xem là như nhau nếu chúng có thể nhận được nhau qua một phép quay quanh tâm của đường tròn ngoại tiếp đa giác.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[luugiangnam]

Câu a ra đáp án giống anh Lữ mà lập luận khá mơ hồ ( sơ sơ thế này , ban đầu là (78,23 ) sau đó cho 1 xanh vào thì A, B cùng giảm 1, cho 2 xanh vào thì 1 là cả 2 cùng giảm 2 hoặc cả 2 cùng giảm 1 , cứ thể ta được KQ như trên.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[modular]

Post này là của huynhcongbang

--------------

A. Ta định nghĩa một nhóm các đỉnh xanh là một dãy các đỉnh xanh liên tiếp trên đường tròn và bị chặn hai đầu bởi màu đỏ. Tương tự với nhóm các đỉnh đỏ.
Rõ ràng số nhóm đỉnh xanh phải bằng số nhóm đỉnh đỏ.
Đặt các nhóm lượng đỉnh trong các đỏ là $r_1,r_2,...,r_k $ và số lượng đỉnh trong các nhóm xanh là $b_1,b_2,...,b_k $.

Hơn nữa, trong một nhóm có kích thước là $t$ thì số cặp đỉnh cùng màu là $t-1$.
Khi đó, ta có $A = \sum_{i=1}^k (r_i-1)$ và $B = \sum_{i=1}^k (b_i-1)$.
Ngoài ra, ta cũng có: $\sum_{i=1}^k r_i = 79, \sum_{i=1}^k b_i = 24$.
Từ đó suy ra $A = 79-k$ và $B=24-k$.
Ta cần có $1 \le k \le 24$ và dễ dàng suy ra có 24 cặp cặp $(A,B)$ có dạng $(A,B)=(79-k,24-k)$ với $k=1,2,3,...,24$.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[huynhcongbang]

B. Theo câu a thì với $B=14$, ta tìm được số nhóm $k=24-14=10$.
Khi đó, ta có $b_1+b_2+...+b_{10}=24$ và $r_1+r_2+...+r_{10}=79$.

Ta thấy ứng với mỗi bộ $(b_1,b_2,...,b_{10})$ và một bộ $(r_1,r_2,...,r_{10})$ là các bộ nghiệm nguyên dương của hai phương trình trên thì có đúng 1 cách tô thỏa mãn đề bài.

Do đó, theo bài toán chia kẹo Euler, số cách tô cần tìm là $C_{23}^{9}. C_{78}^{9}$.

Mong là không có sai sót gì!

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

[whatever2507]

Nguyên văn bởi huynhcongbang

B. Theo câu a thì với $B=14$, ta tìm được số nhóm $k=24-14=10$.
Khi đó, ta có $b_1+b_2+...+b_{10}=24$ và
$r_1+r_2+...+r_{10}=79$.

Ta thấy ứng với mỗi bộ $(b_1,b_2,...,b_{10})$ và một bộ $(r_1,r_2,...,r_{10})$ là các bộ nghiệm nguyên dương của hai phương trình trên thì có đúng 1 cách tô thỏa mãn đề bài.

Do đó, theo bài toán chia kẹo Euler, số cách tô cần tìm là $C_{23}^{10}. C_{78}^{10}$.

Mong là không có sai sót gì!

Đếm kẹo Euler thì chỉ ra $C_{23}^9.C_{78}^9$ thôi chứ anh . Với cả em nghĩ phải chia $10$ lần lặp vì bộ $(b_1,b_2,...,b_{10})$ và bộ $(r_1,r_2,...,r_{10})$ khi xếp lên đường tròn sẽ trùng với bộ $(b_i,...,b_{10},b_1,...,b_{i-1})$ và $(r_i,...,r_{10},r_1,...,r_{i-1})$ với mọi $i$ từ 1 đến 10. Đáp số cuối cùng của em là $\frac{C_{23}^9.C_{78}^9}{10}$
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[huynhcongbang]

Nguyên văn bởi whatever2507

Đếm kẹo Euler thì chỉ ra $C_{23}^9.C_{78}^9$ thôi chứ anh . Với cả em nghĩ phải chia $10$ lần lặp vì bộ $(b_1,b_2,...,b_{10})$ và bộ $(r_1,r_2,...,r_{10})$ khi xếp lên đường tròn sẽ trùng với bộ $(b_i,...,b_{10},b_1,...,b_{i-1})$ và $(r_i,...,r_{10},r_1,...,r_{i-1})$ với mọi $i$ từ 1 đến 10. Đáp số cuối cùng của em là $\frac{C_{23}^9.C_{78}^9}{10}$

Oh, anh nhớ nhầm tí. Anh đã sửa lại rồi.

Còn chuyện trùng nhau này thì để nghĩ thêm tí coi, chắc phải vẽ ra vài bộ mới dễ thấy được.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[hoangqnvip]

Câu a ta có thể giải ra bằng 1 nhận xét sau:
Với mọi cách tô màu ta đều có $A-B=55$ và không đổi
Từ đây suy ra các giá trị $(A,B)$ là $(55,0);,,,;(78,23)$
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[Fool's theorem]

Câu b lúc đầu mình cũng ra đáp số giống bạn ĐM cơ mà thử cho mấy th nhỏ thì cái số kia chưa chắc đã nguyên.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[let_wind_go]

Chán quá mình cũng chia kẹo euler nhưng lại ra $\frac{1}{10}.C_{23}^9$ vì cứ tưởng ứng với một cách tô xanh thì điểm đỏ xác định duy nhất, phí quá
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[ahhungah]

Em ra khác rồi các bác @@. C14/24*C9/78
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[vinhhop.qt]

Nguyên văn bởi ahhungah

Em ra khác rồi các bác @@. C14/24*C9/78

Minh nghi day la ket qua dung.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[Traum]

Câu a: giả sử ta tô màu xanh 24 đỉnh là $1\le a_1 < a_2 < ... <a_{24}\le 103 $. Khi đó đặt $b_i = a_{i+1}-a_{i}\ge 1 $ với $1\le i\le 23 $ và $b_{24} = 103 + a_1 - a_{24}\ge 1 $.
Ta có đẳng thức: $b_1 + b_2 + \cdots+b_{24} = 103 $. Nhận xét rằng số giữa hai điểm xanh $a_i $ và $a_{i+1} $ thì có $b_i-1 $ điểm đỏ và từ $b_i-1 $ điểm đỏ này sẽ cho ta $b_i-2 $ cặp đỏ-đỏ nếu $b_i\ge 2 $ và cho ta 0 cặp đỏ-đỏ nếu $b_i\le 1 $. Do đó nếu có $K $ số $b_i = 1 $ thì có $0\le K\le 23 $ $24-K $ số $b_i\ge 2 $.
Số cặp đỏ là $\sum\limits_{b_i\ge 2}b_i-2 = \sum\limits_{b_i\ge 2}b_i - 2(24-K) = \sum\limits_{b_i\ge 1}b_i - \sum\limits_{b_i=1}b_i -2(24-K) = 103 - K - 2(24-K) = 55 + K $.
Ngược lại với mỗi $0\le K\le 24 $ thì tồn tại $b_1,b_2,...,b_{24} $ thỏa mãn có đúng $K $ số bằng 1 và tổng tất cả bằng 103. Ví dụ $b_{i} = 1 $ với $1\le i\le K $, $b_{i} = 2 $ với $K+1\le i\le 23 $ và $b_{24} = 57+K $. Vậy ta có số cặp đỏ-đỏ và xanh-xanh luôn có dạng $(55+K,K) $ với $0\le K\le 23 $.

Câu b: Trước hết ta tính số cách tô màu các đỉnh xanh thỏa mãn với $a_1 = 1, a_{24} = 103 $. Khi đó ta có $b_1 + b_2 + \cdots +b_{23} = a_{24}-a_{1} = 102 $. Từ điều kiện có đúng 14 cặp xanh-xanh nên ta có trong 23 số $b_i $ có đúng 13 số bằng 1. Số cách chọn $13 $ số này là $\binom{23}{13} = \binom{23}{10} $. Số cách chọn 10 số còn lại là $\binom{102-23-1}{10-1} = \binom{78}{9} $.

Lại có với mỗi cách tô màu sao cho có 14 cặp xanh-xanh thì bằng cách xoay quanh tâm ta có có đúng 14 cách tô màu sao cho $a_1=1,a_{24} = 103 $. Việc còn lại là chứng minh với mọi cách tô thì việc quay quanh tâm không trùng với chính nó. Giả sử ngược lại thì ta có tồn lại các số nguyên dương $1\le l \le 102 $ sao cho hai tập $X = \{a_1,a_2,\dots a_{24}\} $ và $Y = \{a_1+l,a_2 + l,...,a_{24} + l\} \pmod {103} $ trùng nhau. Khi đó ta có $\sum\limits_{i=1}^{24}(a_i + l)\equiv \sum\limits_{i=1}^{24}a_i \pmod {103} $ suy ra $24l\equiv 0\pmod {103} $. Điều này không xảy ra với $1\le l\le 102 $.

Từ tất cả nhận xét trên thì số cách tô màu thỏa mãn bài toán là: $\frac{\binom{23}{10}\binom{78}{9}}{14} = \frac{\binom{23}{9}\binom{78}{9}}{10} = \frac{\binom{24}{10}\binom{78}{9}}{24} $
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[huynhcongbang]

Vậy là bài tổ hợp có thể tự tin với kết quả là $\frac{C_{78}^9 C_{23}^9}{10}$ rồi.

Các cách khác cũng áp dụng các bước sắp xếp nhưng theo thứ tự khác nên biểu thức cũng hơi khác thôi, đều cùng kết quả cả.

Mình xin share một cách phân tích trên trang Sputnik Education, mọi người tham khảo thử nhé!

Bài 3. Câu a khá là đơn giản. Số đỉnh màu xanh là 24 đỉnh = 103 - 79. Nếu tất cả các đỉnh đỏ chụm thành 1 cụm thì A = 78, nếu bị cắt ahfnh 2 cụm thì A = 77 và cứ thế: tức là nếu có k cụm (mỗi cụm là các đỉnh cùng màu đỏ đứng sát nhau) thì A = 79-k. Nếu có k cụm đủ thì cũng có k cụm xanh, nên B = 24-k. Các giá trị có thể của k là từ 1 đến 24, nên có 24 khả năng tất cả.

Câu b khá là khó. Để có B = 14 thì k =10 (phải chia quân xanh thành 10 cụm, quân đỏ thành 10 cụm). Đếm số cách chia như thế nào ?

Ta thử đánh số các cụm xanh từ 1 đến 10, bắt đầu từ 1 cụm nào đó. Gọi số phần tử của 10 cụm đó (theo thứ tự vòng tròn thuận chiều kim đồng hồ) là x1, ... x10. Khi đó các số y1=x1, y2=x1+x2, v.v., y9 = x1+...+x9 (y10 =24 là cố định, không tính), là các số dương khác nhau từ 1 đến 23 (không thể là 24). Có C(9,23) cách chọn 9 số đó từ 23 số. Như vậy là có C(9,23) cách chia 24 quân xanh thành 10 cụm (có xếp hàng). Tương tự như vậy, có C(9,78) cách chia quân đỏ. Nhân với nhau được C(9,23)C(9,78) Mỗi cách cho ta một cách xếp (tô màu): đầu tiên xếp cụm 1 quân xanh, rồi đến cụm 1 quân đỏ, rồi đến cụm 2 quân xanh, v.v. (Vì có thể quay vòng tròn, nên ta có thể coi "điểm bắt đầu" là điểm đầu của cụm 1 quân xanh). Vì sao 2 cách xếp khác nhau ở đây lại không trùng nhau khi quay vòng tròn ?! (Nếu chẳng may trùng nhau thì rắc rối to, phải tìm cách nào loại đi sự trùng nhau, bằng cách băm nhỏ rồi chia như thế nào đó). Nhưng may thay, số 79 là số nguyên tố nên sẽ không có hai cách nào trùng nhau ! Do vậy số cách sẽ là C(9,23)C(9,78). Nhưng có 10 cách chọn điểm bắt đầu (vì có 10 cụm quân xanh) cho cùng 1 cách tô màu, nên phải chia số C(9,23)C(9,78) cho 10, được kết quả cuối cùng là C(9,23)C(9,78)/10.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[quocbaoct10]

Câu a thì giá trị như thế nào cũng không ảnh hưởng nên gọi số điểm đỏ là a và số điểm xanh là 103-a. chỉ cần xét các mô hình điểm, nếu đổi chỗ 2 điểm xanh và đỏ bất kì thì A và B sẽ cùng tăng 1 nếu nó có cấu hình $(...AABABA...) \rightarrow (...AAABBA...)$ , không thay đổi nếu nó có cấu hình $(...ABBABB...) \rightarrow(...ABABBB...)$ hoặc (...BAABAA...)->(...BABAAA...) và giảm 1 nếu có cấu hình $(...AABB...) \rightarrow (...ABAB...)$... nên từ đó ta chỉ có thể nhận được các bộ $(A,B)=(a-k,103-a-k)$

chắc còn vài kiểu cấu hình nữa , nãy giờ ngồi dùng chia kẹo , mất thời gian quá

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

[Fool's theorem]

Mình k nghĩ chia 10 là đúng đâu. Lí do là trong nghiệm ta xét thì các bộ $(m_i,n_i)$ chưa chắc đã phân biệt nên chưa chắc mỗi cái đã lặp đúng 10 lần.
Thử với t/h nhỏ hơn sẽ thấy sai đó là
$n_1+n_2+n_3+n_4=4$
$m_1+m_2+m_3+m_4=6$
Nếu dùng đúng ct thì sẽ là $\frac{C^3_3 C^3_5}{4}$ k phải là số nguyên
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]