17.7. Question 10

So question 10 we want to prove a universally quantified statement. Namely, we want to prove that you take any integer f, there is always a multiple of f which has only the digits 0’s and 1’s in its decimal expansion.

The statement we are trying to prove is that for any integer 'f', we can find a number which is a multiple of 'f' and consists only of the digits '0' and '1' in its decimal format. A universally quantified statement means it must hold true for all possible values of 'f', not just specific cases.

Think of it like finding a special type of lock (the multiple of f) that can be opened using a specific key (the number made up of 0's and 1's). No matter which lock you have (different integers), there exists a key (a corresponding number) that will fit.

Before going into the proof if you want to take few examples say f = 1 then I always have the number 1 which is a multiple of 1 and which has only the digit 1 in its decimal expansion. Remember it is not mandatory that you have both 0’s as well as 1 in the decimal expansion.

For the integer 'f'=1, the number '1' itself is the simplest example of a multiple of 'f', displaying only the digit '1'. If 'f'=2, then '10' is a valid multiple because it is equal to '2 times 5' and uses only 0's and 1's. The case with 'f'=3 and the number '111' shows how we can generate combinations that still adhere to the rule.

It’s like having a vending machine that only gives a specific type of snack (the multiple of f). If you put in different amounts (the integers), you might get different snacks that still follow these rules. For instance, if you always put in 1 dollar, you always get a snack without any extra ingredients (just 1).

But this is a universally quantified statement and we cannot prove a universally quantified statement just showing examples for a few cases. So we have to give the proof for arbitrary f.

While examples help illustrate the point, they do not provide a formal proof. To establish that the statement is true for any integer 'f', a general proof method is necessary. Thus, we utilize the pigeonhole principle, a fundamental concept in combinatorics that allows us to reason about the existence of certain relationships between a set of items.

Imagine you have a box (the set of integers) and you want to distribute a fixed number of balls (0's and 1's) into it. To say a few boxes already have balls doesn't mean all boxes do. To confirm that every box can have one ball requires you to show a systematic way to do it, just as we do in our proof.

Again, we are going to apply here the pigeonhole principle. So let me define a few decimal numbers here. I define the first decimal number to be 1. I define the second decimal number as 11, the i-th decimal number as a decimal number consisting of n number of 1’s and the f+1 decimal number which has the digit 1, f+1 number of times.

In constructing our proof, we create a series of decimal numbers, each consisting entirely of the digit '1'. The first number is simply '1', the second '11', the third '111', and so on. This forms a basis for the possible multiples we will be examining, structured as a function that relates the number of '1's to the integer 'f'.

Think of these decimal numbers like building blocks: each block is a '1'. You can stack 1 block, then 2 blocks, and so on. Just as you can create taller and taller structures, we can create larger numbers, ensuring they still adhere to our foundational rule about digits.

Now what can I say about this remainders? It is easy to see that these remainders belong to the set 0 to f−1 because of the simple fact that you divide any number by n, the only possible remainders could be 0 if it is completely divisible by f or the remainders could be 1, 2 … f−1.

Using the pigeonhole principle, we recognize that there are 'f' possible remainders when dividing by 'f', but we have 'f+1' numbers created from our decimal representations. This guarantees that at least two of those numbers will share the same remainder when divided by 'f'. This is crucial because the same remainders indicate that we can form a number divisible by 'f'.

Imagine you have a classroom of students (the numbers) sharing a limited number of lockers (the remainders from 0 to f-1). If there are more students than lockers, at least two must share a locker. This overlapping ensures that certain conditions are met, as in our case where two formed numbers yield the same remainder.

So if I take n – m then this will be a decimal number which will have trailing 0’s and then at the leading positions you will have the 1’s. That means it is a decimal number which has only the characters 1’s and 0’s.

The difference between our two numbers that give the same remainder produces a number consisting of only '1's followed by '0's. This structure clearly adheres to the requirement of having only digits '0' or '1' in its decimal form. Furthermore, since the two original numbers were both multiples of 'f', their difference must also be a multiple of 'f'. Hence, we've proven the original statement.

Think of creating a pattern in a painting. If your paint colors are limited to just black (1) and white (0), you can create complex patterns (the numbers) that stick to these colors. No matter how many patterns you create (the multiples), as long as they’re composed of black and white, they will always fit your artistic restrictions.

--