Author |
Topic: Strings of 9s (Read 9353 times) |
|
Eric Yeh
Senior Riddler
Gender: 
Posts: 318
|
 |
Re: NEW PROBLEM: Factoring 9s
« Reply #25 on: Sep 11th, 2002, 9:37pm » |
 Quote  Modify
|
Heehee, you're so funny Chronos! I meant it as a joke, but since you are taking it seriously, I guess I can too!!!  So how SURE are you of your guesses? Surely there are multiple "Eric Yeh"s that appear on your Google search? Can't my early posts simply be due to a fanaticism in puzzles?? And can you ascertain my studies or current work? (Your hypotheses seem unsubstantiated at the moment -- and you didn't even hypothesize my [supposed] graduate work!) Where'd the currently programming note come from? And I did indeed mean based on the content of my posts, but your resourcefulness is noted!!
Not a bad start though! Should I post this as a "real" problem??! JK!!! (Seriously.)
Best,
Eric
|
|
 IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: NEW PROBLEM: Factoring 9s
« Reply #26 on: Sep 11th, 2002, 10:45pm » |
Quote Modify
|
Here's a more elementary proof. It uses only the pigeonhole principle and the unique factorization theorem.
Assume that none of the integers in the set Sn = {101-1, ..., 10n-1} is divisible by n, where n is not divisible by 2 or 5. By the pigeonhole principle, at least two of these integers must have the same remainder when divided by n -- there are n integers in the set, and only n-1 distinct remainders available since 0 has been ruled out. Let 10j-1, 10k-1 be one such pair, with n >= j > k > 0. Then n divides their difference, (10j-1) - (10k-1) = 10j - 10k = (10j-k - 1)(10k). That is, there exists an integer m such that mn = (10j-k - 1)(10k).
Consider the prime factorization of each side of this equation. By the unique factorization theorem, each of the 2's and 5's that make up the factorization of the 10k on the right must appear in the factorization of either n or m on the left. But we are given that n is not divisible by 2 or 5, so all the factors must come from m. Thus we know that m' = m/10k is an integer, and m'n = 10j-k - 1. But j-k < n, so 10j-k - 1 is an element of Sn. This contradicts our assumption that no such numbers are divisible by n.
Therefore there exists an element of Sn that is divisible by n.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: NEW PROBLEM: Factoring 9s
« Reply #27 on: Sep 12th, 2002, 5:52am » |
Quote Modify
|
Tim,
Nice pf -- it also easily generalizes to the sharper bound of phi(n). I should mention, however, that while UFT is perhaps a more intuitive concept, a true proof of it from basic principles is no more elementary than our previous proof. In fact, the most direct path generally leads through the Diophantine Result as well, and then requires one more "big step" to get the UFT.
Best,
Eric
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: NEW PROBLEM: Factoring 9s
« Reply #28 on: Sep 15th, 2002, 10:29pm » |
Quote Modify
|
Quote:| So how SURE are you of your guesses? |
|
I'm not SURE in a physicist's sense of SURE, but then, a physicist never is that sure. And I figured you were joking, but it was fun to play along.
As for the specifics: I found a mention of an "Eric Yeh" at Berkeley, in a CS paper on the construction of an image wand. The Harvard connection was a page on "Where are math grads now?", which listed an "Eric Yeh" as currently being a programmer. Based on the dates for these two references, I suspected that Berkeley was undergrad and Harvard was grad. There might be multiple folks named "Eric Yeh", but how many could there really be associated with Harvard, and with a strong mathematical inclination?
And based on the content of posts alone, I would have guessed programmer or mathematician anyway.
|
|
IP Logged |
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: NEW PROBLEM: Factoring 9s
« Reply #29 on: Sep 16th, 2002, 12:34pm » |
Quote Modify
|
Chronos,
Fair enough. However, I have no affiliation with Berkeley. And worse yet, only five fingers on my left hand.
Happy Puzzling,
Eric
|
| « Last Edit: Sep 16th, 2002, 12:35pm by Eric Yeh » |
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
titan
Newbie
Posts: 33
|
|
Re: Strings of 9s
« Reply #30 on: Oct 16th, 2013, 7:57am » |
Quote Modify
|
Can somebody please prove this:
1/n will be a repeating decimal if n is not divisible by 2 or 5
|
|
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Strings of 9s
« Reply #31 on: Oct 16th, 2013, 8:58am » |
Quote Modify
|
on Oct 16th, 2013, 7:57am, titan wrote:Can somebody please prove this:
1/n will be a repeating decimal if n is not divisible by 2 or 5 |
|
Long division algorithm + pigeonhole principle.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Strings of 9s
« Reply #32 on: Oct 16th, 2013, 9:37am » |
Quote Modify
|
It will also be repeating if it is divisible by 2 or 5. You just have to write out the '0's: 1/4 = 0.25000... .
Even without being divisible by 2 or 5, there is already the case of n=1: 1/n = 1.000... .
|
|
IP Logged |
|
|
|
Dmitriy
Newbie
Posts: 1
|
|
Re: Strings of 9s
« Reply #33 on: May 12th, 2014, 3:14pm » |
Quote Modify
|
Here is a simple solution to the original problem.
Suppose among the first n numbers 9, 99, 999, ... there are no numbers divisible by n. Then at least two of these numbers (e.g. 99 and 99999) must have the same remainder when divided by n. Subtracting them, we get a number (e.g.99900) divisible by n. But because n does not contain factors of 2 and 5, that would mean 999 is divisible by n. Done!
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print