// Numbas version: exam_results_page_options {"name": "Counting 2: the pigeonhole principle", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"statement": "

The pigeonhole principle states that:

\n

If $p$ items are placed into $n$ containers, then there exists a container which has at least $\\left\\lceil \\dfrac{p}{n} \\right\\rceil$ items.

\n

Recall that the ceiling function $\\lceil x\\rceil$ is the smallest integer greater than or equal to $x$. For example $\\lceil \\var{e0} \\rceil = \\var{a0}$.

", "variables": {"a0": {"definition": "random(2..9)", "description": "", "name": "a0", "group": "Ungrouped variables", "templateType": "anything"}, "p1": {"definition": "random((n1+1)..(2n1-1))", "description": "", "name": "p1", "group": "Ungrouped variables", "templateType": "anything"}, "a3": {"definition": "random(3..7 except a2)", "description": "", "name": "a3", "group": "Ungrouped variables", "templateType": "anything"}, "a4": {"definition": "random(3..9 except [a2,a3])", "description": "", "name": "a4", "group": "Ungrouped variables", "templateType": "anything"}, "n3": {"definition": "ceil(p2/(a3-1))-1", "description": "", "name": "n3", "group": "Ungrouped variables", "templateType": "anything"}, "n2": {"definition": "random(10..19)", "description": "", "name": "n2", "group": "Ungrouped variables", "templateType": "anything"}, "a1": {"definition": "ceil(p1/n1)", "description": "", "name": "a1", "group": "Ungrouped variables", "templateType": "anything"}, "e0": {"definition": "a0 - random(1..999)/1000", "description": "", "name": "e0", "group": "Ungrouped variables", "templateType": "anything"}, "n1": {"definition": "random(4..9)", "description": "", "name": "n1", "group": "Ungrouped variables", "templateType": "anything"}, "a2": {"definition": "ceil(p2/n2)", "description": "", "name": "a2", "group": "Ungrouped variables", "templateType": "anything"}, "p2": {"definition": "random((2*n2+1)..(4*n2-1))", "description": "", "name": "p2", "group": "Ungrouped variables", "templateType": "anything"}}, "preamble": {"js": "", "css": ""}, "ungrouped_variables": ["n1", "p1", "n2", "p2", "a2", "a1", "e0", "a0", "n3", "a3", "a4"], "tags": [], "variablesTest": {"maxRuns": 100, "condition": "ceil(p2/n3)=a3"}, "rulesets": {}, "variable_groups": [], "functions": {}, "extensions": [], "metadata": {"description": "

Definition of the pigeonhole principle, and some examples

", "licence": "Creative Commons Attribution-ShareAlike 4.0 International"}, "parts": [{"correctAnswerFraction": false, "mustBeReduced": false, "variableReplacements": [], "maxValue": "{a1}", "correctAnswerStyle": "plain", "type": "numberentry", "mustBeReducedPC": 0, "showFractionHint": true, "customMarkingAlgorithm": "", "variableReplacementStrategy": "originalfirst", "allowFractions": false, "showCorrectAnswer": true, "showFeedbackIcon": true, "extendBaseMarkingAlgorithm": true, "prompt": "

If $\\var{p1}$ pigeons sleep in $\\var{n1}$ nests, then there exists a nest with at least $\\left\\lceil \\dfrac{\\var{p1}}{\\var{n1}}\\right\\rceil$ pigeons. Evaluate $\\left\\lceil \\dfrac{\\var{p1}}{\\var{n1}}\\right\\rceil$.

", "minValue": "{a1}", "useCustomName": false, "unitTests": [], "customName": "", "marks": 1, "notationStyles": ["plain", "en", "si-en"], "scripts": {}}, {"correctAnswerFraction": false, "mustBeReduced": false, "variableReplacements": [], "maxValue": "{a2}", "correctAnswerStyle": "plain", "type": "numberentry", "mustBeReducedPC": 0, "showFractionHint": true, "customMarkingAlgorithm": "", "variableReplacementStrategy": "originalfirst", "allowFractions": false, "showCorrectAnswer": true, "showFeedbackIcon": true, "extendBaseMarkingAlgorithm": true, "prompt": "

If $\\var{p2}$ pigeons sleep in $\\var{n2}$ nests, then there exists a nest with at least how many pigeons?

", "minValue": "{a2}", "useCustomName": false, "unitTests": [], "customName": "", "marks": 1, "notationStyles": ["plain", "en", "si-en"], "scripts": {}}, {"vsetRangePoints": 5, "variableReplacements": [], "failureRate": 1, "type": "jme", "valuegenerators": [], "customMarkingAlgorithm": "", "showPreview": true, "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "showFeedbackIcon": true, "extendBaseMarkingAlgorithm": true, "checkVariableNames": false, "prompt": "

\n

If some number of pigeons sleep in $\\var{n2}$ nests, what is the smallest number of pigeons needed to guarantee there are at least $\\var{a4}$ pigeons in one of the nests?

", "useCustomName": false, "unitTests": [], "customName": "", "vsetRange": [0, 1], "checkingType": "absdiff", "answer": "{n2*(a4-1)+1}", "marks": 1, "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": "

If $\\var{p2}$ pigeons sleep in some number of nests, what is the largest possible number of nests such that there is guaranteed to be at least $\\var{a3}$ pigeons in one of the nests?

", "useCustomName": false, "unitTests": [], "customName": "", "vsetRange": [0, 1], "checkingType": "absdiff", "answer": "{n3}", "marks": 1, "checkingAccuracy": 0.001, "scripts": {}}], "name": "Counting 2: the pigeonhole principle", "advice": "

a. $\\left\\lceil \\dfrac{\\var{p1}}{\\var{n1}}\\right\\rceil = \\var{a1}$.

\n

Of course, all $\\var{p1}$ pigeons could choose to sleep in the same nest. The pigeonhole principle only provides a lower bound on how many pigeons must be in the same nest.

\n

b. $\\left\\lceil \\dfrac{\\var{p2}}{\\var{n2}}\\right\\rceil = \\var{a2}$.

\n

\n

\n

c. Writing $p$ for the number of pigeons, by the pigeonhole principle we have $\\left\\lceil \\dfrac{p}{\\var{n2}}\\right\\rceil \\geq \\var{a4}$. 

\n

Then $ \\dfrac{p}{\\var{n2}} > \\var{a4-1}$, and so $p > {\\var{n2}}\\times{\\var{a4-1}}$.

\n

Since $p>\\var{n2*(a4-1)}$, the smallest integer value of $p$ is $\\var{n2*(a4-1)+1}$.

\n

d. Writing $n$ for the number of nests, if $\\left\\lceil \\dfrac{\\var{p2}}{n}\\right\\rceil \\geq \\var{a3}$,

\n

then $ \\dfrac{\\var{p2}}{n} > \\var{a3-1}$ and so $\\dfrac{\\var{p2}}{\\var{a3-1}} > n$.

\n

Since $\\dfrac{\\var{p2}}{\\var{a3-1}} = \\var{p2/(a3-1)} > n$, the largest integer value of $n$ is $\\var{n3}$.

", "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/"}]}