Bài Toán Chia Kẹo Của Euler

     
*
" data-medium-file="https://i0.wp.com/nangngucnoisoi.vn/wp-content/uploads/2019/10/education-teaching-kid-school-schooling-pupils-school_kids-jwhn192_low.jpg?fit=223%2C300&ssl=1" data-large-file="https://i0.wp.com/nangngucnoisoi.vn/wp-content/uploads/2019/10/education-teaching-kid-school-schooling-pupils-school_kids-jwhn192_low.jpg?fit=640%2C860&ssl=1" data-lazy-srcset="https://i0.wp.com/nangngucnoisoi.vn/wp-content/uploads/2019/10/education-teaching-kid-school-schooling-pupils-school_kids-jwhn192_low.jpg?w=800&ssl=1 800w, https://i0.wp.com/nangngucnoisoi.vn/wp-content/uploads/2019/10/education-teaching-kid-school-schooling-pupils-school_kids-jwhn192_low.jpg?resize=223%2C300&ssl=1 223w, https://i0.wp.com/nangngucnoisoi.vn/wp-content/uploads/2019/10/education-teaching-kid-school-schooling-pupils-school_kids-jwhn192_low.jpg?resize=768%2C1032&ssl=1 768w, https://i0.wp.com/nangngucnoisoi.vn/wp-content/uploads/2019/10/education-teaching-kid-school-schooling-pupils-school_kids-jwhn192_low.jpg?resize=762%2C1024&ssl=1 762w" data-lazy-sizes="(max-width: 800px) 100vw, 800px" data-lazy-src="https://nangngucnoisoi.vn/wp-content/uploads/2019/10/education-teaching-kid-school-schooling-pupils-school_kids-jwhn192_low.jpg?is-pending-load=1" srcset="data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7"> trong những bài toán đếm ta chạm chán bài toán sau: Một fan vào cửa ngõ hang mua phương pháp học tập để gia công thành một món quà có viết, sách với tập, bạn đó chỉ mua tổng cộng 5 món đồ. Hiểu được trong siêu thị có 5 cây viết tương đương nhau, 6 sách như thể nhau cùng 10 cuốn tập giống như nhau, hỏi gồm bao nhiêu cách chọn viết, sách tập để triển khai quà?

Ta thấy rằng con số các viết sách cùng tập đều lớn hơn số cần mua, do đó bài toán chỉ trở lại việc đếm là gồm bao nhiêu bộ sách viết tập nhưng mà tổng số là 5 cái, trong số ấy mỗi cái gồm hoặc ko có.

Bạn đang xem: Bài toán chia kẹo của euler

Có ba đối tượng người tiêu dùng là viết, sách và tập, tạ kí hiệu là $A = V, S, T $. Một món quà tất cả 5 cái, cho nên vì vậy quà hoàn toàn có thể là $X = V, V, V, S, T $, có 3 cây viết cùng 1 sách, 1 tập, hay những tập $Y = V, V, S, T, T $, ta thấy các đối tượng người sử dụng $V, T$ là lập lại. Lúc ấy ta nói tổng hợp $X, Y$ là tổ hợp lặp.

Để có mang rõ rộng ta gồm định nghĩa sau:

Định nghĩa.  cho tập $A = a_1, a_2, cdots, a_k $. Một ánh xạ trường đoản cú $p: A mapsto mathbbN $, khi ấy $P$ được gọi là một trong những multiset của A.

Ví dụ 1. đến $A = a, b, c $. Ánh xạ $p: A mapsto mathbbN$ như sau: $p(a) = 2, p(b) = 1, p(c) = 1$. Khi ấy ta hoàn toàn có thể kí hiệu $p$ là $(aabc)$, xuất xắc $(baac)$,.., không tính đến sản phẩm tự của các thành phần $a, b, c$.

Đặt $n = p(a_1) + p(a_2)+cdots +p(a_k)$, bài xích toán đề ra là tất cả bao nhiêu ánh xạ $p: A mapsto mathbbN$ cơ mà $n = p(a_1) + p(a_2)+cdots +p(a_k)$.

Tiếp theo lấy một ví dụ trên, ví như $ p(a) + p(b) + p(c) = 2$ thì có các multiset sau: $(ab), (ac), (bc), (aa), (bb), (cc)$, 6 multiset.

Tính chất. Cho tập $A = a_1, a_2, cdots, a_k $, số ánh xạ $p: A mapsto mathbbN$ thỏa $p(a_1) + cdots + p(a_k) = n$ là $C^n_n+k-1$


Mỗi ánh xạ $p$ ta cho tương xứng với một dãy nhị phân độ lâu năm $n+k-1$, trong số ấy $p(a_1)$ chữ số đầu là 0, tiếp theo sau là số 1, rồi $p(a_2)$ chữ số $0$,…cuối cùng là $p(a_k)$ chữ số $0$. Ví dụ cỗ $VVSTT$ ứng với dãy $0010100$.

Rõ ràng đó là tương ứng 1 – 1, vì vậy số ánh xạ $p$ thông qua số dãy nhị phân, vì vậy ta chỉ việc đếm số dãy nhị phân.

Ta thấy dãy gồm $n+k-1$ chữ số trong những số ấy có $k-1$ chữ số $1$, do đó số dãy nhị phân chỉ nên số cách chọn vị trí mang đến $k-1$ chữ số $1$ bắt buộc số hàng nhị phân là $C^k-1_n+k-1$.

Do kia số ánh xạ $p$ là $C^k-1_n+k-1 $

Trở lại việc trên, ta thấy số món quà tất cả 5 cái là một trong tổ đúng theo lặp chập 5 của sách, viết, tập, vì thế số món quà rất có thể là $C^2_5+2-1 = C^2_6 = 15$.

Xem thêm: Nồi Cơm Điện Tiết Kiệm Điện, Top 4 Nồi Cơm Điện Ít Hao Điện Không Thể Bỏ Qua

(Chú ý trong vấn đề trên, bảo vệ số mỗi nhiều loại sản phẩm có khá nhiều hơn 5 cái).

Bài toán 1. (Chia kẹo Euler). mang đến $n$ viên kẹo kiểu như nhau đem chia cho $k$ người, hỏi tất cả bao nhiều cách chia.


*
*

Trước hết phát cho mỗi người một viên, thì còn $n-k$ viên kẹo, liên tục áp dụng việc trên cùng với $n-k$. Lúc đó số cách chia là

$C^k-1_n-1$

Ta rất có thể giải câu hỏi trên mà lại không cần áp dụng bài toán 1 bằng cách xây dựng dãy nhị phân thỏa: $a_1$ chữ số đầu là 0, tiếp theo sau là số 1, tiếp là $a_2$ chữ số 0, …., cuối cùng là $a_k$ chữ số 0. Dãy này có $k-1$ chữ số 1 đứng giữa $n$ chữ số 0 và không có hai chữ số $1$ làm sao đứng kề nhau. Lúc đó số dãy nhị phân là: $C^k-1_n-1$.


Phần kế tiếp ta cùng mày mò và giải một trong những bài toán hoàn toàn có thể đưa về bài toán tổng hợp lặp hay bài toán chia kẹo Euler. Các bạn chờ nhé.

Bài toán 1 với 2 rất có thể phát biểu bên dưới dạng sau.

Bài toán 3. cho phương trình $x_1 + x_2 + cdots + x_k = n$ trong các số đó $k, n$ là các số nguyên dương.

a. Kiếm tìm số nghiệm tự nhiên của phương trình.

b. Kiếm tìm số nghiệm nguyên dương của phương trình.

Xem thêm: At The End Of This Month Or In The End Of This Month? By The End Of The Month

Như bài toán trên ta vẫn biết, số nghiệm tự nhiên của phương trình là $C^k-1_n+k-1$.