Combinatorics homework question

[buzzmath]

Can anyone help with this proof?

Let k be an element of positive integers. prove that there exists a positive integer n such that k|n and the only digits in n are 0's and 3's

This is in section on the pigeon hole principle and the only problem I have left. I'm not really sure where to begin on it. Thanks

 

[neurocomp2003]

k|n stands for k divides n right? not n divides k?

if a number n only consists of the numbers {0,3}
what other property do you know of such a number?
not sure why youd need the pigeon hoel principle to prove it though.

 

[AKG]

Hmm... I first thought to look at some number M, and see how many positive integers there were from 1 to M (A), how many multiples of k there were from 1 to M (B), and how many numbers from 1 to M had only 0's and 3's (C). I planned on finding a good choice of M such that B + C > A, then using the pigeonhole principle to argue that some multiple of k must be all 0's and 3's, but this never seemed to work, and probably never will (I tried choosing M to be things like 10^m, k^m, and 333...333 (with m 3's)).

Now, I'm thinking to look at all m-digit numbers that have all 0's and 3's. The least such number is 3 x 10^m-1, and the greatest is 333...333 (m 3's). There are, in total, 2^m-1 such numbers. Now what we're essentially looking for is a number of all 0's and 3's that is congruent to 0 (mod k). Suppose that for some m, k | 3 x 10^m-1. Then we're done. Otherwise, if the m digits numbers that are all 0's and 3's occupy, say, j congruence classes (mod k), then the m+1 digit numbers occupy at least j+1 congruence classes. Continuing, there must be some M such that the M digit numbers that are all 0's and 3's contain (all) k congruence classes (mod k), so in particular, one of them belongs to the congruence class of 0 (mod k), which is exactly what we're looking for. Maybe in a weird way, this is pigeonhole principle.

 

[buzzmath]

thanks a lot. I think I get it now.

 

[0rthodontist]

Wait, but why couldn't you have all of the m digit numbers that are all 0's and 3's occupy, for example, just one congruence class mod k?

Here is a way I think it can be done, in terms of paper multiplication by digits. This is a needlessly inefficient procedure because I can't be bothered to implement actual paper multiplication but the basic idea is to choose the next digits of some number x so that kx = n, starting from the rightmost digit of x and working to the left, so that you always end up with a 0 or a 1 in the next digit of the product. And once you are done with the z'th digit of x from the right, none of the more significant digits of x will ever affect the digit n that the z'th digit of x is responsible for. This can be seen clearly by working out some paper multiplication.

Find-01's(k = (k0 ... kn)) // kn ... k0 are the decimal digits of k, least significant to most

 let i = 0 // i indicates x
 let d = 1 //d cycles through digits
 let x = (x0, x1, ...) = (0, 0, 0, ... ) //x is an infinite string of digits
 let p = (p0, p1, ...) = (0, 0, 0, ...) //p is the product
 while true //this loops until something inside it returns
  for d = 1 to 9
   let xi = d //xi is the ith digit of x
   let p = (x * k)
   if pi = 1 or pi = 0 //pi is the i'th digit of p
    goto mid
  end for
  return error //if you reach this line you could not find a correct digit and my argument is incorrect
mid:
  if k | p 
   let p = p * 3
   return p
  let i = i + 1
 end while

This algorithm rests on the idea that for any number w and any digit v, it is possible to find a digit u between 1 and 9 such that u * v + w has a least significant bit of 0 or 1. I don't know that this is true, but an exhaustive search of all digits w = 0..9 and all digits v = 0..9 could verify or disprove it. Why the algorithm rests on this can be seen by trying it with paper multiplication but is hard to describe here. Basically when you paper multiply you have a string of digits that is shifted from the right margin by a certain number of spaces, and the least significant digit of p that your current digit of x is able to fix, is equal to the sum of the digits written above it in the paper multiplication thing, plus the product of your current digit of x and the least significant bit of k. If you can always manage to make that 0 or 1 without resorting to letting the current digit of x be 0, then x will have a finite number of digits and it will eventually produce a product containing all 1's and 0's.

Here's an example, running the algorithm on the input 7
k = (7)
x = (0, ...)
iteration zero: when x = (3, ...), kx = 21 (or (1, 2, ...)) and the zero'th bit of kx is 1
iteration one: when x = (3, 4, ...), kx = 301 (or (1, 0, 3)) and the first bit of kx is 0.
iteration three: when x = (3, 4, 1, ...), kx = 1001 (or (1, 0, 0, 1)) and the second bit of kx is 0
Now 7 divides 1001 so the output is 3003.

 

[AKG]

Let's call numbers with only 0's and 3's nice. Suppose that the m digit nice numbers occupy j congruence classes (mod k). Then we may pick a set J(m) of j distinct m digit nice numbers such that no two are congruent (mod k). Suppose there is some element x of J(m) congruent to 0 (mod k). Then we're done. Otherwise, assume that J(m) has no such elements. Now consider the set

$$J(m+1) = \{3 \times 10^m + x\ |\ x = 0\ \vee \ x \in J(m)\}$$

This clearly gives j+1 distinct m+1 digit nice numbers. Are they all incongruent (mod k)? Well if two are congruent, then we'd have distinct numbers x and y (elements of J(m) U {0}) such that:

3 x 10^m + x = 3 x 10^m + y (mod k)
x = y (mod k)

Both x and y cannot be 0, since we've stipulated that x and y are distinct. If neither are 0, then we have two congruent (mod k) elements of J(m), contradicting the choice of J(m). The only remaining possibility is that one of them is 0, and the other is in J(m), but if this is the case, then there is some x in J(m) congruent to 0 (mod k), contradicting the assumption that J(m) has no multiples of k. So in all cases, we get a contradiction, and this contradiction is occurring within the scope of the assumption that the j+1 elements J(m+1) are not all incongruent. So they are all incongruent. In fact, we know that J(1) = {3} fills out one congruence class (mod k), so we know, from the above argument, that J(k) fills out the congruence classes (mod k).

 

[AKG]

This algorithm rests on the idea that for any number w and any digit v, it is possible to find a digit u between 1 and 9 such that u * v + w has a least significant bit of 0 or 1.

Which boils down to:

for any digit w and any digit v, there is a non-zero digit u such that uv + w = 0 or 1 (mod 10)

which boils further down to:

for any digit w' and any digit v, there is a non-zero digit u such that uv = w' or w'+1 (mod 10)

This is false: take v = 5, w' = 1, 2, 3, 6, 7, or 8.

So, going back to:

This algorithm rests on the idea that for any number w and any digit v, it is possible to find a digit u between 1 and 9 such that u * v + w has a least significant bit of 0 or 1.

Take v = 5, and let w be any number with least significant bit 2, 3, 4, 7, 8, or 9. Then clearly it is impossibly to find any u, let alone a u between 1 and 9, such that uv+w has least significant bit 0 or 1. At a glance, it appears that if v is not equal to 5, however, then for any w, you can find a nonzero digit u such that uv + w has least significant bit 0 or 1.

 

[0rthodontist]

All right then, patch on the algorithm: if the last digit of k is 5, then divide k by 5 until the last digit of k is not 5 before starting the while loop. Also if the last digit of k is 0, then divide k by 10 until the last digit of k is not 0. Then you can simply multiply your final result p by 10 the same total number of times that you divided.

Assuming 5 and 0 are the only digits it fails on.