จำนวนชุดค่าผสมที่ $x_1+x_2+x_3=100$ ถ้าสำหรับทุกๆ $3\ge i\ge 1$, $x_i$ เป็นจำนวนเต็มที่ไม่เป็นลบกับ $40\ge x_i$
ฉันเพิ่งเจอคำถามต่อไปนี้:
ค้นหาจำนวนชุดค่าผสมที่ $x_1+x_2+x_3=100$ ถ้าสำหรับทุกๆ $3\ge i\ge 1$, $x_i$ เป็นจำนวนเต็มที่ไม่เป็นลบกับ $40\ge xi$.
ฉันแก้ไขด้วยวิธีต่อไปนี้โดยแยกออกเป็นอินสแตนซ์ต่างๆ
ถ้า $x_1=20$: 1 วิธีแก้ปัญหา ($x_2=40, x_3=40$)
ถ้า $x_1=21$: 2 วิธีแก้ปัญหา
ถ้า $x_1=22$: 3 โซลูชั่น
$\ldots$
ถ้า $x_1=40$: 21 วิธีแก้ปัญหา
เนื่องจากผลรวมที่ได้คือการเพิ่มความก้าวหน้าทางคณิตศาสตร์เราจึงมี $1+2+\ldots+21=\frac{(1+21) \cdot 21}{2}=\frac{21 \cdot 22}{2}=231$
ฉันพบคำถามนี้ในบทที่เกี่ยวข้องกับหลักการยกเว้นการรวม แต่ฉันคิดไม่ออกว่าจะแก้อย่างไรโดยใช้หลักการยกเว้นการรวม ใครช่วยช่วยแสดงวิธีแก้ปัญหาที่เป็นระเบียบของคำถามนี้ให้ฉันด้วยการใช้หลักการรวม - ยกเว้นโดยอธิบายด้วยว่าเขาคิดโดยสังหรณ์ใจว่าจะดำเนินการต่อไปในแต่ละขั้นตอนอย่างไร
คำตอบ
คำตอบเฉพาะของสมการ $$x_1 + x_2 + x_3 = 100 \tag{1}$$ สอดคล้องกับตำแหน่งของ $3 - 1 = 2$ สัญญาณเพิ่มเติมในแถวของ $100$คน ตัวอย่างเช่นหากเราวางเครื่องหมายเพิ่มเติมไว้หลัง$20$th และ $60$พวกเราได้รับการแก้ปัญหา $x_1 = 20$, $x_2 = 40$, $x_3 = 40$ (นับจำนวนคนทางด้านซ้ายของเครื่องหมายบวกแรกสำหรับค่าของ $x_1$ระหว่างเครื่องหมายบวกทั้งสองสำหรับค่าของ $x_2$และทางด้านขวาของเครื่องหมายบวกทั้งสองสำหรับค่าของ $x_3$). ดังนั้นจำนวนคำตอบของสมการในจำนวนเต็มที่ไม่เป็นค่าลบคือ$$\binom{100 + 3 - 1}{3 - 1} = \binom{102}{2}$$ เนื่องจากเราต้องเลือกสองตัวเลือก $102$ ตำแหน่งที่จำเป็นสำหรับ $100$ หนึ่งและสองสัญญาณเพิ่มเติมจะเต็มไปด้วยเครื่องหมายเพิ่มเติม
จากสิ่งเหล่านี้เราต้องลบกรณีที่ตัวแปรหนึ่งตัวหรือมากกว่านั้นเกิน $40$.
ตัวแปรเกิน $40$: มีสามวิธีในการเลือกว่าตัวแปรใดเกิน $40$. สมมติว่าเป็น$x_1$. แล้ว$x_1' = x_1 - 41$เป็นจำนวนเต็มไม่ติดลบ การแทนที่$x_1' + 41$ สำหรับ $x_1$ ในสมการที่ 1 ให้ผลตอบแทน \begin{align*} x_1' + 41 + x_2 + x_3 & = 100\\ x_1 + x_2 + x_3 & = 59 \tag{2} \end{align*} สมการ 2 คือสมการในจำนวนเต็มไม่ลบที่มี $$\binom{59 + 3 - 1}{3 - 1} = \binom{61}{2}$$แนวทางแก้ไข ดังนั้นมี$$\binom{3}{1}\binom{61}{2}$$ โซลูชันที่ค่าของตัวแปรเกิน $40$.
อย่างไรก็ตามหากเราลบจำนวนนี้ออกจากผลรวมเราจะลบแต่ละกรณีที่มีตัวแปรเกินสองตัว $40$ สองครั้งสำหรับแต่ละวิธีในการกำหนดตัวแปรหนึ่งในสองตัวแปรนั้นเป็นตัวแปรที่เกิน $40$. เราต้องการลบกรณีดังกล่าวเพียงครั้งเดียวดังนั้นเราจึงต้องบวกลงในผลรวม
เกินสองตัวแปร $40$: มี $\binom{3}{2}$ วิธีเลือกตัวแปรสองตัวที่เกิน $40$. สมมติว่าพวกเขาเป็น$x_1$ และ $x_2$. แล้ว$x_1' = x_1 - 41$ และ $x_2' = x_2 - 41$เป็นจำนวนเต็มไม่ติดลบ การแทนที่$x_1' + 41$ สำหรับ $x_1$ และ $x_2' + 41$ สำหรับ $x_2$ ในสมการที่ 1 ให้ผลตอบแทน \begin{align*} x_1' + 41 + x_2' + 41 + x_3 & = 100\\ x_1' + x_2' + x_3 & = 18 \tag{3} \end{align*} สมการ 3 คือสมการในจำนวนเต็มไม่ลบที่มี $$\binom{18 + 3 - 1}{3 - 1} = \binom{20}{2}$$แนวทางแก้ไข ดังนั้นมี$$\binom{3}{2}\binom{20}{2}$$ การแก้ปัญหาที่สองตัวแปรเกิน $40$.
ดังนั้นโดยหลักการรวม - การยกเว้นจำนวนคำตอบของสมการ 1 ที่ไม่มีตัวแปรเกิน $40$ คือ $$\binom{102}{2} - \binom{3}{1}\binom{61}{2} + \binom{3}{2}\binom{20}{2} = 231$$ ตามที่คุณพบ
$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ โดย $\ds{\ \underline{definition}}$คำตอบได้รับจาก: \begin{align} &\bbox[5px,#ffd]{\sum_{x_{1} = 1}^{40} \sum_{x_{2} = 1}^{40}\sum_{x_{3} = 1}^{40}\ \overbrace{\bracks{z^{100}}z^{x_{1}\ +\ x_{2}\ +\ x_{3}}} ^{\ds{\delta_{x_{1}\ +\ x_{2}\ +\ x_{3}{\large ,} 100}}}\ =\ \bracks{z^{100}}\pars{\sum_{x = 1}^{40}z^{x}}^{3}} \\[5mm] = &\ \bracks{z^{100}}\pars{z\,{z^{40} - 1 \over z - 1}}^{3} \\[5mm] = &\ \bracks{z^{97}}\pars{1 - z^{40}}^{3}\pars{1 - z}^{-3} = \bracks{z^{97}}\pars{1 - 3z^{40} + 3z^{80}}\pars{1 - z}^{-3} \\[5mm] = &\ \bracks{z^{97}}\pars{1 - z}^{-3} - 3\bracks{z^{57}}\pars{1 - z}^{-3} + 3\bracks{z^{17}}\pars{1 - z}^{-3} \\[5mm] = &\ {-3 \choose 97}\pars{-1}^{97} - 3{-3 \choose 57}\pars{-1}^{57} + 3{-3 \choose 17}\pars{-1}^{17} \\[5mm] = &\ \underbrace{{99 \choose 97}}_{\ds{4851}}\ -\ 3\ \underbrace{{59 \choose 57}}_{\ds{1711}}\ +\ 3\ \underbrace{{19 \choose 17}}_{\ds{171}}\ =\ \bbx{\large 231} \end{align}