Let \(n\) be a composite number. Arrange the factors of \(n\) greater than \(1\) in a circle. When can this be done such that neighbours in the circle are never coprime?
Let \(x\), \(y\), \(z\) and \(w\) be non-negative integers. Find all solutions to \(2^x3^y-5^z7^w=1\).
A robot is programmed to move along the number line starting at \(2\). At each second, the number by which it moves up by must be a factor of the number it’s currently on, but not \(1\). For example, if the robot gets to \(10\), then it can move forward by \(2\), \(5\) or \(10\) steps, going to \(12\), \(15\), or \(20\). What numbers can it land on, and what numbers can’t it land on?
A gang of three jewel thieves has stolen some gold coins and wants to divide them fairly. However, they each have one unusual rule: (i) The first thief wants the number of coins to be divisible by \(3\) so they can split it evenly. (ii) The second thief wants the number of coins to be divisible by \(5\) because she wants to split her share with her four siblings. (iii) The third thief wants the number of coins to be divisible by \(7\) since he wants to split his share amongst seven company stocks.
However, they’re stuck as the number of coins isn’t divisible by any of these numbers. In fact, the number of coins is \(1\) more than a multiple of \(3\), \(3\) more than a multiple of \(5\) and \(5\) more than a multiple of \(7\).
What’s the smallest number of coins they could have? (And if you’re feeling generous, how would you help them out?)
Show that if \(1+2+\dots+n = \frac{n(n+1)}{2}\), then \(1+2+\dots+(n+1) = \frac{(n+1)((n+1)+1)}{2}\).
Show that \(1+2+\dots+n = \frac{n(n+1)}{2}\) for every natural number \(n\).
Show that if \(1+2^1+2^2+\dots+2^{10} = 2^{11} - 1\), then \(1+2^1+2^2+\dots+2^{11} = 2^{12} - 1\).
Show that \(1+2^1+2^2+\dots+2^n = 2^{n+1} - 1\) for every natural number \(n\).
What is wrong with the following proof that “all rulers have the same length" using induction?
Base case: suppose that we have one ruler, then clearly it clearly has the same length as itself.
Assume that any \(n\) rulers have the same length for the induction hypothesis. If we have \(n+1\) rulers, the first \(n\) ruler have the same length by the induction hypothesis, and the last \(n\) rulers have the same length also by induction hypothesis. The last ruler has the same length as the middle \(n-1\) rulers, so it also has the same length as the first ruler. This means all \(n+1\) rulers have the same length.
By the principle of mathematical induction, all rulers have the same length.
Given a series of statements enumerated by the natural numbers, the strong induction principle says the following. Suppose that
The 1st statement is true (the base case).
Whenever all statements up to and including the \(n\)th statement is true, the \((n+1)\)th statement is also true (induction step).
Then the statement is true for all natural numbers. Show that the strong induction principle works.