// Numbas version: exam_results_page_options {"name": "Counting 2: integer soln to linear equation", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"statement": "

The number of non-negative integer solutions to the equation

$x_1 + x_2 + \\cdots + x_{r} = n$

is $C(n+r-1,r-1)$. The following questions invite you to explore variations of this identity.

Remember that the NUMBAS syntax for $C(n,r)$ is comb(n,r).

", "variables": {"b": {"definition": "random((r*(a+1)+1)..(2*r*(a+1)+1))", "description": "", "name": "b", "group": "Ungrouped variables", "templateType": "anything"}, "a": {"definition": "random(3..5)", "description": "", "name": "a", "group": "Ungrouped variables", "templateType": "anything"}, "n": {"definition": "random(filter(0=mod(n,2),n,(2*(b+1)+1)..(3*(b+1)-1)))", "description": "", "name": "n", "group": "Ungrouped variables", "templateType": "anything"}, "r": {"definition": "random(4..6)", "description": "", "name": "r", "group": "Ungrouped variables", "templateType": "anything"}}, "preamble": {"js": "", "css": ""}, "ungrouped_variables": ["r", "n", "a", "b"], "tags": [], "variablesTest": {"maxRuns": 100, "condition": "n<100"}, "rulesets": {}, "variable_groups": [], "functions": {}, "extensions": [], "metadata": {"description": "

Couting application where repitition is allowed and order does not matter.

", "licence": "Creative Commons Attribution-ShareAlike 4.0 International"}, "parts": [{"vsetRangePoints": 5, "variableReplacements": [], "failureRate": 1, "type": "jme", "valuegenerators": [], "customMarkingAlgorithm": "", "showPreview": true, "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "showFeedbackIcon": true, "extendBaseMarkingAlgorithm": true, "checkVariableNames": false, "prompt": "

How many non-negative integer solutions are there to the equation

$x_1 + x_2 + \\cdots + x_{\\var{r}} = \\var{n}$

with no further restrictions?

", "useCustomName": false, "unitTests": [], "customName": "", "vsetRange": [0, 1], "checkingType": "absdiff", "answer": "{comb(n+r-1,r-1)}", "marks": 1, "checkingAccuracy": 0.001, "scripts": {}}, {"stepsPenalty": 0, "variableReplacements": [], "failureRate": 1, "type": "jme", "valuegenerators": [], "customMarkingAlgorithm": "", "showPreview": true, "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "showFeedbackIcon": true, "vsetRangePoints": 5, "extendBaseMarkingAlgorithm": true, "checkVariableNames": false, "prompt": "

How many non-negative integer solutions are there to the equation

$x_1 + x_2 + \\cdots + x_{\\var{r}} = \\var{n}$

with each $x_j \\geq \\var{a}$?

", "useCustomName": false, "unitTests": [], "customName": "", "vsetRange": [0, 1], "checkingType": "absdiff", "answer": "{comb(n-r*a+r-1,r-1)}", "steps": [{"prompt": "

Assume that $x_j \\geq \\var{a}$. We cannot use the above formula directly on this equation, so instead let's reformulate the question in terms of the new variable $y_j = x_j - \\var{a} \\geq 0$:

$y_1 + y_2 + \\cdots + y_{\\var{r}} = (x_1 - \\var{a}) +(x_2 - \\var{a}) + \\cdots (x_{\\var{r}} - \\var{a}) = \\var{n} - \\var{a}\\times \\var{r} = \\var{n-a*r}$.

You can think of $y_j$ as representing the 'extra' bit that $x_j$ has on top of $\\var{a}$. Now we can apply the above formula because the only restriction is that $y_j \\geq 0$.

", "variableReplacements": [], "useCustomName": false, "unitTests": [], "type": "information", "customName": "", "customMarkingAlgorithm": "", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "showFeedbackIcon": true, "marks": 0, "extendBaseMarkingAlgorithm": true, "scripts": {}}], "marks": 1, "checkingAccuracy": 0.001, "scripts": {}}, {"stepsPenalty": 0, "variableReplacements": [], "failureRate": 1, "type": "jme", "valuegenerators": [], "customMarkingAlgorithm": "", "showPreview": true, "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "showFeedbackIcon": true, "vsetRangePoints": 5, "extendBaseMarkingAlgorithm": true, "checkVariableNames": false, "prompt": "

How many non-negative integer solutions are there to the equation

$x_1 + x_2 + \\cdots + x_{\\var{r}} = \\var{n}$

where each $x_j$ is even?

", "useCustomName": false, "unitTests": [], "customName": "", "vsetRange": [0, 1], "checkingType": "absdiff", "answer": "{comb(n/2+r-1,r-1)}", "steps": [{"prompt": "

Assume that $x_j$ is even then define the new variable $y_j = \\frac{1}{2} x_j$. Then

$\\displaystyle y_1 + y_2 + \\cdots + y_{\\var{r}} = \\frac{x_1 +x_2 + \\cdots x_r}{2} = \\var{n/2}$.

Now we can apply the above formula because the only restriction is that $y_j \\geq 0$.

How many non-negative integer solutions are there to the equation

$x_1 + x_2 + \\cdots + x_{\\var{r}} = \\var{n}$

with each $x_j \\leq \\var{b}$?

", "useCustomName": false, "unitTests": [], "customName": "", "vsetRange": [0, 1], "checkingType": "absdiff", "answer": "{comb(n+r-1,r-1) - comb(r,1)*comb(n-(b+1)+r-1,r-1) + comb(r,2)*comb(n-2*(b+1)+r-1,r-1)}", "steps": [{"vsetRangePoints": 5, "variableReplacements": [], "failureRate": 1, "type": "jme", "valuegenerators": [], "customMarkingAlgorithm": "", "showPreview": true, "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "showFeedbackIcon": true, "extendBaseMarkingAlgorithm": true, "checkVariableNames": false, "prompt": "

Let $U$ be the set of solutions without any restriction, and let $S_j$ be the set of solutions where $x_j > \\var{b}$.

The size of $S_1$ can be found by replacing $x_1$ with $y_1=x_1-\\var{b+1}\\geq 0$ and applying the given forumula. What is the size of $S_1$?

", "useCustomName": false, "unitTests": [], "customName": "", "vsetRange": [0, 1], "checkingType": "absdiff", "answer": "{comb(n-(b+1)+r-1,r-1)}", "marks": 0, "checkingAccuracy": 0.001, "scripts": {}}, {"vsetRangePoints": 5, "variableReplacements": [], "failureRate": 1, "type": "jme", "valuegenerators": [], "customMarkingAlgorithm": "", "showPreview": true, "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "showFeedbackIcon": true, "extendBaseMarkingAlgorithm": true, "checkVariableNames": false, "prompt": "

What is the size of $S_1 \\cap S_2$? That is, how many solutions arise when $x_1$ is replaced with $y_1=x_1-\\var{b+1}\\geq 0$ and $x_2$ is replaced with $y_2=x_2-\\var{b+1}\\geq 0$?

", "useCustomName": false, "unitTests": [], "customName": "", "vsetRange": [0, 1], "checkingType": "absdiff", "answer": "{comb(n-2*(b+1)+r-1,r-1)}", "marks": "0", "checkingAccuracy": 0.001, "scripts": {}}, {"vsetRangePoints": 5, "variableReplacements": [], "failureRate": 1, "type": "jme", "valuegenerators": [], "customMarkingAlgorithm": "", "showPreview": true, "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "showFeedbackIcon": true, "extendBaseMarkingAlgorithm": true, "checkVariableNames": false, "prompt": "

What is the size of $S_1 \\cap S_2 \\cap S_3$?

", "useCustomName": false, "unitTests": [], "customName": "", "vsetRange": [0, 1], "checkingType": "absdiff", "answer": "0", "marks": "0", "checkingAccuracy": 0.001, "scripts": {}}, {"prompt": "

The above answers imply we can ignore counting all cases when more than two of the $x_i$ terms are greater than $\\var{b}$.

So by the inclusion/exclusion principle, the answer is

$\\left|U\\right| - \\left(\\left|S_1\\right| +\\left|S_2\\right| + \\cdots + \\left|S_\\var{r}\\right| \\right) + \\left(\\left|S_1 \\cap S_2\\right| + \\left|S_1 \\cap S_3\\right| + \\cdots+ \\left|S_{\\var{r-1}}\\cap S_\\var{r}\\right|\\right)$

These questions are about using a change of variable to make the question about non-negative integer solutions. Read the expanded parts above for more detailed information in each case.

", "contributors": [{"name": "Daniel Mansfield", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/743/"}, {"name": "Sean Gardiner", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/2443/"}]}]}], "contributors": [{"name": "Daniel Mansfield", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/743/"}, {"name": "Sean Gardiner", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/2443/"}]}