wu :: forums
« wu :: forums - Strings of 9s »

Welcome, Guest. Please Login or Register.
Mar 28th, 2024, 5:20pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: ThudnBlunder, william wu, Grimbal, SMQ, Icarus, towr, Eigenray)
   Strings of 9s
« Previous topic | Next topic »
Pages: 1 2  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Strings of 9s  (Read 9299 times)
Eric Yeh
Senior Riddler
****





   
Email

Gender: male
Posts: 318
Re: NEW PROBLEM: Factoring 9s  
« Reply #25 on: Sep 11th, 2002, 9:37pm »
Quote Quote Modify 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!!!  Wink  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!!  Wink
 
Not a bad start though!  Should I post this as a "real" problem??!  Wink  Wink  Wink  JK!!!  (Seriously.)
 
Best,
Eric
IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
TimMann
Senior Riddler
****






   
WWW

Gender: male
Posts: 330
Re: NEW PROBLEM: Factoring 9s  
« Reply #26 on: Sep 11th, 2002, 10:45pm »
Quote Quote Modify 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
****





   
Email

Gender: male
Posts: 318
Re: NEW PROBLEM: Factoring 9s  
« Reply #27 on: Sep 12th, 2002, 5:52am »
Quote Quote Modify 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
***





   
WWW Email

Gender: male
Posts: 288
Re: NEW PROBLEM: Factoring 9s  
« Reply #28 on: Sep 15th, 2002, 10:29pm »
Quote Quote Modify 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
****





   
Email

Gender: male
Posts: 318
Re: NEW PROBLEM: Factoring 9s  
« Reply #29 on: Sep 16th, 2002, 12:34pm »
Quote Quote Modify Modify

Chronos,
 
Fair enough.  However, I have no affiliation with Berkeley.  And worse yet, only five fingers on my left hand.
 
Happy Puzzling,  Wink
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 Quote Modify 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: male
Posts: 880
Re: Strings of 9s  
« Reply #31 on: Oct 16th, 2013, 8:58am »
Quote Quote Modify 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: male
Posts: 7526
Re: Strings of 9s  
« Reply #32 on: Oct 16th, 2013, 9:37am »
Quote Quote Modify 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 Quote Modify 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 Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board