I give you an arbitrary positive integer x > 0. You write down x, 2x, 3x, 4x, ..., kx in decimal. How large much k be to guarantee that every digit appears somewhere in your list, regardless of x?
Considering that x could be 2, we can conclude that k must be at least 45. I don't know whether k be larger than 45 or not. David Cantrell ----- Original Message ----- From: "David Wilson" <davidwwilson@comcast.net> To: "Math Fun" <math-fun@mailman.xmission.com> Sent: Thursday, December 15, 2011 12:48:22 PM Subject: [math-fun] Puzzler I give you an arbitrary positive integer x > 0. You write down x, 2x, 3x, 4x, ..., kx in decimal. How large much k be to guarantee that every digit appears somewhere in your list, regardless of x? _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
David Cantrell:
Considering that x could be 2, we can conclude that k must be at least 45. I don't know whether k be larger than 45 or not.
It is 72, I think, for x = 125. David Wilson:
I give you an arbitrary positive integer x > 0. You write down x, 2x, 3x, 4x, ..., kx in decimal. How large much k be to guarantee that every digit appears somewhere in your list, regardless of x?
Hans Havermann:
It is 72, I think, for x = 125.
Yes, you are right. It seems likely that 72 should suffice for all integers x. One may extend the question to arbitrary nonzero real numbers x; write down the decimal expansions of x, 2x, 3x, 4x, ..., kx. We need a convention for the digit 0, but let us count any occurrence of 0 after the leading nonzero digit of the number, including the case that the expansion is terminating. (When x is an integer, we need not bother with 0, as it always appears as early as in 10x.) Note that the smallest possible k in the "real" case is an upper bound on the smallest possible k in the "integer" case. I claim that k = 81 in the "real" case. Note that this k is required for x = 1/9, because ax contains no 9 for a<81. To prove the claim, first note that it suffices to look at numbers x between 1/10 and 1. We divide into three cases, depending on how x relates to 1/9 and 10/81. Case 1: 1/10 <= x < 1/9. Then we may pick k = 10, because ax contains the digit a for a<10, and x contains a (non-leading) 0. Case 2: 1/9 < x < 10/81. By an argument similar to the one of Michael Kleber, all nonzero digits have appeared at least once as a leading digit as soon as kx is at least 9. Moreover, 9x contains a 0, because 1 < 9x < 10/9. Picking k minimal, we get (k-1)x < 9, and so k < 9/x + 1 < 82; hence we may pick k = 81. Case 3: 10/81 <= x < 1. Again, all nonzero digits have appeared as a leading digit as soon as kx is at least 9. To make sure we also find a 0, pick k such that kx is at least 10. For the smallest such k, we have that kx contains a 0, because 10 <= kx < 11. This time, we get (k-1)x < 10, and so k < 10/x + 1 <= 82; hence again we may pick k = 81. I hope I got things right. Jakob
Certainly k=100 suffices: (a) The number 10x is one digit longer than x, which means that adding x can change the lead digit by at most 1. (b) Both 10x and 100x start with the same digit as x. (c) Together these imply that by the time you've made it to 100x, you've cycled through every lead digit. Note that all of (a), (b), and (c) are base-independent statements :-). I suspect David's k=45 (for base 10) is the correct answer, but don't immediately see how to pull the upper bound that low. --Michael On Thu, Dec 15, 2011 at 8:47 AM, <dwcantrell@comcast.net> wrote:
Considering that x could be 2, we can conclude that k must be at least 45. I don't know whether k be larger than 45 or not.
David Cantrell
----- Original Message -----
From: "David Wilson" <davidwwilson@comcast.net> To: "Math Fun" <math-fun@mailman.xmission.com> Sent: Thursday, December 15, 2011 12:48:22 PM Subject: [math-fun] Puzzler
I give you an arbitrary positive integer x > 0.
You write down x, 2x, 3x, 4x, ..., kx in decimal.
How large much k be to guarantee that every digit appears somewhere in your list, regardless of x?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
participants (5)
-
David Wilson -
dwcantrell@comcast.net -
Hans Havermann -
Jakob Jonsson -
Michael Kleber