Puzzles and Problems

  1. Write 1000000 as the product of two whole numbers, neither of which ends in 0. Solution.
  2. With how many 0’s does the number 100! end? Solution. What about 200! ? Solution.
  3. Show that a number is divisible

                              (i)            by 3 if, and only if, the sum of its digits (in base ten) is divisible by 3; Solution;

                            (ii)            by 9 if, and only if, the sum of its digits (in base ten) is divisible by 9; Solution;

                           (iii)            by 11 if, and only if, the difference between the sum of its odd-placed digits and the sum of its even-placed digits (in base ten) is divisible by 11.
(For example, 92807363 gives (9 + 8 + 7 + 6) - (2 + 0 + 3 + 3) = 22, which is divisible by 11.) Solution.

The number 430725275 is in base eight. Is it divisible by 7? Solution.

  1. Let p be a prime number, not 2, and let q be the next prime number after p. Prove that p + q is the product of at least three prime factors, not necessarily distinct.
    (For example, 3 + 5 = 2 ´ 2 ´ 2; 5 + 7 = 2 ´ 2 ´ 3; 7 + 11 = 2 ´ 3 ´ 3; 11 + 13 = 2 ´ 2 ´ 2 ´ 3; 13 + 17 = 2 ´ 3 ´ 5; etc.) Solution.
  2. Is it possible to find a positive integer n such that all of the numbers n, n + 1, n + 2, ¼, n + 100 are composite (that is, not prime)? Solution.
  3. The sequence 2, 5, 11, 23, 47 consists of five primes, each being one more than double the previous one. Find another such sequence (consisting of five primes, each being one more than double the previous one). Solution.
  4. Let A = {1, 4, 7, ¼ }, the set of all numbers of the form 3n + 1, where n = 1, 2, 3, ¼. If p is in A, and p > 1, and p does not factorise as the product of two smaller numbers in A, then let us call p a prim. (It is almost prime!) Prove that A contains infinitely many prims. Show also that A contains numbers that factorise into prims in more than one way (that is, with different prim factors). Solution.
  5. Let a, b, c, d be positive integers with ab = cd. Prove that a2 + b2 + c2 + d2 is composite. Solution.
  6. Hardy’s taxi-number, 1729, is (famously) the smallest positive integer that can be written as the sum of two cubes in two different ways: 1729 = 1000 + 729 = 103 + 93 and 1729 = 1728 + 1 = 123 + 13.
    What is the smallest positive integer that can be written as the sum of two (non-zero) squares in two different ways?
    What is the smallest positive integer that can be written as the sum of two (non-zero) squares in three different ways? Solution.
  7. If n is a positive integer, in base ten, then the reverse of n is the number formed by writing the digits of n in reverse order. So, for example, the reverse of 4263 is 3624.

                              (i)            A positive integer is a palindrome if it is equal to its reverse; for example, 252 is a palindrome. Find the least palindrome which is divisible by 13, and find any palindrome which is divisible by 54. Solution.

                            (ii)            Let us call a positive integer a pseudo-palindrome if it divides its reverse. So every palindrome is (trivially) a pseudo-palindrome. Apart from palindromes, then, are there any pseudo-palindromes? Solution.

  1. Ted Glenn has just emptied the coins from his pockets onto the counter in the shop. “I need some stamps,” he says, “first or second class, or some of each¾I don’t mind¾but I want to get rid of all this change!” Mrs. Goggins scratches her head. “I don’t think that is possible,” she says. If she is right, what is the largest sum of money Ted could have put on the counter? (1st class stamps are 27p each, and 2nd class stamps are 19p each.) Solution.
  2. Find all positive integers a, b, c with a < b < c and such that the following are all true: a is a factor of bc - 1; b is a factor of ca - 1; and c is a factor of ab - 1. Solution.
  3. One way of proving that there are infinitely many primes goes like this: start with 2, which is prime; 2 + 1 = 3, another prime; 2 ´ 3 + 1 = 7, another prime; 2 ´ 3 ´ 7 + 1 = 43, another prime; 2 ´ 3 ´ 7 ´ 43 + 1=1807, not a prime, but equal to 23 ´ 89 giving two more primes; and so on. At each stage you multiply together all the primes you have found so far, and add 1, which either gives a “new” prime, or factorises to give two or more “new” primes. Prove that this process never produces the prime 5. Solution.
  4. An integer polynomial f(x) is a sum of (non-negative, integer) powers of x multiplied by (positive, negative or zero) integer coefficients. So, for example, x3 - 3x + 7 (that is, 1 ´ x3 + 0 ´ x2 + (-3) ´ x1 + 7 ´ x0) is an integer polynomial. For such a polynomial f(x), we shall only allow integer values of the variable x; and this ensures that f(x) is always an integer. (We shall also always assume f(x) is not constant.)

                              (i)            Show that the integer polynomial x2 + x + 11 takes only prime values for x = 0, 1, ¼, 9. Can you find an integer polynomial giving a longer “run” of primes? Solution.

                            (ii)            Find an integer polynomial f(x) such that whenever f(x) is positive, it is prime. (Don’t cheat by choosing f(x) so that it is never positive! Make it take as many different prime values as you can.) Solution.

                           (iii)            Let f(x) be an integer polynomial with all its coefficients positive or zero. (But not all of them zero, of course, since f(x) is not constant.) Prove that, for x positive, f(x) cannot always be prime. Solution.

  1. Suppose the following message is received from outer space:
    00110000011000111111110110010011001001100101111000100100010010001001001100110
    Why might it be conjectured that this was sent by a human-like being who has one arm twice as long as the other? Solution.
  2. Alice thinks of an integer in the range 1 to 16. Bob must determine the number by asking questions, each of which requires a “yes” or “no” answer.

                              (i)            How many questions does Bob need to guarantee to find the number?

                            (ii)            How many questions does he need if Alice is allowed to tell one lie? Solution.

  1. A book has been ordered by quoting its ISBN (International Standard Book Number). Unfortunately one of the digits has been smudged and is illegible. The ISBN is the following, with the smudge represented by “y”: 01934651y2. Find y. Solution.
  2. The ENIGMA machine in German military use was complicated by having a plugboard attached with the property of swapping letters in pairs. For instance, if the operator was told to plug together the pairs

(AM)(BT)(CR)(EH)(GX)(KN),

then the effect would be to give an extra permutation of the input and output letters thus:

ABCDEFGHIJKLMNOPQRSTUVWXYZ

MTRDHFXEIJNLAKOPQCSBUVWGYZ

(Note that the letters not mentioned are simply left unchanged.) The cryptanalyst has to discover (amongst other things) which plugboard swapping has been set up. How many possibilities are there to be considered?

                              (i)            Show that there are 325 ways of choosing just ONE pair to be swapped.

                            (ii)            It is harder to count the number when there is more than one pair being swapped. Consider the case for two pairs. Think of yourself as first colouring two of the letters red, two green, and leaving the rest alone. Show that there are (26!)/(2! ´ 2! ´ 22!) ways of doing this. Now, choose the red ones as a swapped pair and the green ones as another swapped pair. Show that this means there are (26!)/(2! ´ 2! ´ 2! ´ 22!) ways of choosing two pairs to be swapped.

                           (iii)            By extending this argument show there are (26!)/(6! ´ 2! ´ 2! ´ 2! ´ 2! ´ 2! ´ 2! ´ 14!) ways of chosing six pairs to be swapped.

                          (iv)            For what number of pairs (i.e., for which number between 0 and 13 inclusive) is the total number of possibilities greatest? Show that this number is 205,552,193,096,250. Solution.