// Numbas version: finer_feedback_settings {"name": "Induktion (Briefmarken)", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"name": "Induktion (Briefmarken)", "tags": [], "metadata": {"description": "

Prove (by induction) that every value $\\ge$ 44ct can be combined by using 5ct and 12ct stamps.

Idea seen in collection of exercises for preparing for the Putnam contest.

", "licence": "Creative Commons Attribution 4.0 International"}, "statement": "

Zeigen Sie: Wenn man genügend viele Briefmarken mit den Werten 5 ct und 12 ct hat, dann lässt sich jeder Brief, der mit 44ct oder mehr frankiert werden muss, mit dem genauen Porto versehen.

Sie sollten zuerst versuchen, diese Aussage selbst zu beweisen. Wenn Sie das hinbekommen, dann brauchen Sie diese Aufgabe eigentlich nicht mehr (aber Sie könnten sie auch sehr schnell lösen). Wenn Sie keine Idee haben, wie Sie vorgehen sollten, oder irgendwo steckenbleiben, dann schauen Sie sich die Aufgabenteile dieser Aufgabe an. Am besten machen Sie aber zwischendurch dann noch mal die eine oder andere Denkpause und überlegen, ob Sie den Beweis selbst zu Ende bringen können.

", "advice": "

Start-Beispiele:

$17 = 1\\cdot 5 + 1\\cdot 12$

$29 = 1\\cdot 5 + 2\\cdot 12$

Nicht-Beispiele:

Die einzigen Werte zwischen $35$ und $45$, die sich nicht durch 5ct- und 12ct-Marken darstellen lassen, sind $38$ und $43$. (Um das zu zeigen, probieren wir einfach durch: $38$, $38-12$, $38-24$, $38-36$ sind sämtlich keine Vielfachen von $5$; mit $43$ geht es ähnlich. Für die anderen Werte ist es nicht schwer, eine geeignete Kombination zu finden.)

Darstellung der Zahlen zwischen $44$ und $48$:

$44 = 4\\cdot 5 + 2\\cdot 12$

$45 = 9\\cdot 5 + 0\\cdot 12$

$46 = 2\\cdot 5 + 3\\cdot 12$

$47 = 7\\cdot 5 + 1\\cdot 12$

$48 = 0\\cdot 5 + 4\\cdot 12$

Beweis der ursprünglichen Aussage:

Induktionsanfang, $n\\in \\{ 44, 45, 46, 47, 48 \\}$: Das haben wir im vorherigen Schritt gesehen.

Induktionsschritt $n>48$. Wir können als Induktionsvoraussetzung annehmen, dass die Behauptung für $n-5, n-4, n-3, n-2$ und $n-1$ richtig ist. Ist $n-5 = 5a+12b$, so ist $n = 5(a+1) + 12b$.

Zusatzfrage:

Im Beweis sehen wir, dass es im Induktionsschritt ausreichend ist, die Anzahl der 5ct-Marken zu erhöhen. Wir müssen also nur schauen, wie viele 12ct-Marken für die Werte zwischen 44ct und 48ct benötigt werden. Wir sehen: 48ct lassen sich nur mit 4 Marken à 12ct erhalten. (Für größere Werte kann man natürlich, wenn man möchte, auch mehr 12ct-Marken benutzen. Was müsste man untersuchen, um herauszubekommen, was die Mindestzahl an 5ct-Marken ist, mit der man alle Werte $\\ge$ 44ct bekommen kann?)

", "rulesets": {}, "extensions": [], "variables": {}, "variablesTest": {"condition": "", "maxRuns": 100}, "ungrouped_variables": [], "variable_groups": [], "functions": {}, "preamble": {"js": "", "css": ""}, "parts": [{"type": "gapfill", "useCustomName": true, "customName": "Start", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [{"label": "Nicht-Beispiele", "rawLabel": "", "otherPart": 1, "variableReplacements": [], "availabilityCondition": "", "penalty": "", "penaltyAmount": 0, "lockAfterLeaving": false}, {"label": "Induktionsanfang", "rawLabel": "", "otherPart": 2, "variableReplacements": [], "availabilityCondition": "", "penalty": "", "penaltyAmount": 0, "lockAfterLeaving": false}], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": "A", "prompt": "

Stellen Sie die folgenden Werte dar, indem Sie Briefmarken zu 5ct und zu 12ct kombinieren:

17 = [[0]] $\\cdot 5 +$ [[1]] $\\cdot 12$.

29 = [[2]] $\\cdot 5 +$ [[3]] $\\cdot 12$.

Hier sollen Sie Werte angeben, die man nicht als Kombination von (gegebenenfalls mehreren) 5ct und 12ct-Briefmarken darstellen kann. Es ist klar, dass das für kleine Werte wie $1, 2, 3, 4, 6, 7, 8, 9, 11$ nicht geht. Bei größeren Zahlen ist es manchmal nicht so klar.

Geben Sie die Menge aller Zahlen zwischen $35$ und $45$ an, die sich nicht als Kombination von 5ct und 12ct-Marken \"darstellen\" lassen. (Mit der set()-Notation, zum Beispiel set(35,36) statt $\\{35, 36\\}$.)

[[0]]

", "gaps": [{"type": "jme", "useCustomName": false, "customName": "", "marks": "2", "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "answer": "set(38,43)", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": 0.001, "failureRate": 1, "vsetRangePoints": 5, "vsetRange": [0, 1], "checkVariableNames": false, "singleLetterVariables": false, "allowUnknownFunctions": true, "implicitFunctionComposition": false, "valuegenerators": []}], "sortAnswers": false}, {"type": "gapfill", "useCustomName": true, "customName": "Induktionsanfang", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [{"label": "Induktionsschritt", "rawLabel": "", "otherPart": 3, "variableReplacements": [], "availabilityCondition": "", "penalty": "", "penaltyAmount": 0, "lockAfterLeaving": false}], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": "A", "prompt": "

In diesem Teil beginnen wir mit einer etwas systematischeren Untersuchung. Geben Sie für die folgenden Zahlen an, wie sie sich durch 5ct- und 12ct-Marken zusammensetzen lassen:

44 = [[0]] $\\cdot 5$ + [[1]] $\\cdot 12$,

45 = [[2]] $\\cdot 5$ + [[3]] $\\cdot 12$,

46 = [[4]] $\\cdot 5$ + [[5]] $\\cdot 12$,

47 = [[6]] $\\cdot 5$ + [[7]] $\\cdot 12$,

48 = [[8]] $\\cdot 5$ + [[9]] $\\cdot 12$.

Denken Sie nun noch einmal über die ursprüngliche Fragestellung nach!

", "gaps": [{"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minValue": "4", "maxValue": "4", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minValue": "2", "maxValue": "2", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minValue": "9", "maxValue": "9", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minValue": "0", "maxValue": "0", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minValue": "2", "maxValue": "2", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minValue": "3", "maxValue": "3", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minValue": "7", "maxValue": "7", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minValue": "1", "maxValue": "1", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minValue": "0", "maxValue": "0", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minValue": "4", "maxValue": "4", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}], "sortAnswers": false}, {"type": "gapfill", "useCustomName": true, "customName": "Induktionsschritt", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [{"label": "Zusatzfrage", "rawLabel": "", "otherPart": 4, "variableReplacements": [], "availabilityCondition": "", "penalty": "", "penaltyAmount": 0, "lockAfterLeaving": false}], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": "A", "prompt": "

Nach dem vorherigen Schritt können wir per Induktion beweisen, dass sich jeder Wert $\\ge$ 44ct aus 5ct- und 12ct-Marken zusammensetzen lässt.

[[0]], $n\\in \\{ 44, 45, 46, 47, 48 \\}$: Das haben wir im vorherigen Schritt gesehen.

Induktionsschritt $n>$ [[1]]. Wir können als Induktionsvoraussetzung annehmen, dass die Behauptung für $n-5, n-4, n-3, n-2$ und $n-1$ richtig ist. Ist $n-5 = 5a+12b$, so ist $n =$ [[2]].

", "gaps": [{"type": "patternmatch", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "answer": "Induktionsanfang", "displayAnswer": "", "matchMode": "exact"}, {"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minValue": "48", "maxValue": "48", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "jme", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": false, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "answer": "5(a+1) + 12b", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": 0.001, "failureRate": 1, "vsetRangePoints": 5, "vsetRange": [0, 1], "checkVariableNames": false, "singleLetterVariables": false, "allowUnknownFunctions": true, "implicitFunctionComposition": false, "valuegenerators": [{"name": "a", "value": ""}, {"name": "b", "value": ""}]}], "sortAnswers": false}, {"type": "gapfill", "useCustomName": true, "customName": "Zusatzfrage", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [{"label": "Nicht-Beispiele", "rawLabel": "", "otherPart": 1, "variableReplacements": [], "availabilityCondition": "", "penalty": "", "penaltyAmount": 0, "lockAfterLeaving": false}], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": "A", "prompt": "

Zusatzfrage: Wie viele 12ct-Marken braucht man mindestens, um alle Werte $\\ge$ 44 kombinieren zu können?

Man braucht mindestens [[0]] von den 12ct-Marken. Die kleinste Zahl, die man nicht mit weniger 12ct-Marken darstellen kann, ist [[1]].