Combinatorics, Induction (Mathematical Induction)

Mathematical Induction is a proof technique used to establish that a statement is true for all natural numbers (or an infinite sequence starting from some integer). It involves a base case and an inductive step. Questions require constructing inductive proofs for formulas, properties, or statements.

• 6 on the Board

  The number 6 is written on the board. At each step, you can add the digit 6 to the end of the number (so that it is the units digit,) or replace the number with the sum of its digits.
  Which numbers can be obtained in this way? Describe the entire set of numbers and explain why there are no more

  Topics:

  Arithmetic Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules -> Divisibility Rules by 3 and 9 Combinatorics -> Induction (Mathematical Induction) Logic -> Reasoning / Logic Number Theory -> Division -> Parity (Even/Odd) Algebra -> Sequences Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • Young Mathematician Olympiad, 2018-2019, Final, Grades 3-4 Question 6
  • Young Mathematician Olympiad, 2018-2019, Final, Grades 5-6 Question 5

• Government Elections

  In the parliamentary elections of a certain country, a number of parties participated (the exact number is unknown). Every citizen who participated in the elections voted for one party.

  For every positive integer k, let `d_k` denote the number of parties that received k or more votes. Prove that the sum `d_1+d_2+d_3+...` is equal to the number of citizens who voted in the elections.

  Show hint

  Log in here to receive the hint
  Topics:

  Combinatorics -> Induction (Mathematical Induction)
  Sources:
  • Grossman Math Olympiad, 2017, Juniors Question 4

• THE WRONG HATS

  "One of the most perplexing things I have come across lately," said Mr. Wilson, "is this. Eight men had been dining not wisely but too well at a certain London restaurant. They were the last to leave, but not one man was in a condition to identify his own hat. Now, considering that they took their hats at random, what are the chances that every man took a hat that did not belong to him?"

  "The first thing," said Mr. Waterson, "is to see in how many different ways the eight hats could be taken."

  "That is quite easy," Mr. Stubbs explained. "Multiply together the numbers, `1, 2, 3, 4, 5, 6, 7`, and `8`. Let me see—half a minute—yes; there are `40,320` different ways."

  "Now all you've got to do is to see in how many of these cases no man has his own hat," said Mr. Waterson."

  Thank you, I'm not taking any," said Mr. Packhurst. "I don't envy the man who attempts the task of writing out all those forty-thousand-odd cases and then picking out the ones he wants."

  They all agreed that life is not long enough for that sort of amusement; and as nobody saw any other way of getting at the answer, the matter was postponed indefinitely. Can you solve the puzzle?

  Topics:

  Combinatorics -> Induction (Mathematical Induction) Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • Amusements in Mathematics, Henry Ernest Dudeney Question 267