wu :: forums « wu :: forums - Strings of 9s » Welcome, Guest. Please Login or Register. Dec 2nd, 2021, 5:46pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: ThudnBlunder, Icarus, SMQ, Eigenray, Grimbal, towr, william wu)    Strings of 9s « Previous topic | Next topic »
 Pages: 1 2 Reply Notify of replies Send Topic Print
 Author Topic: Strings of 9s  (Read 8604 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

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: 7517
 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
 Pages: 1 2 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »