Author 
Topic: Strings of 9s (Read 7774 times) 

Eric Yeh
Senior Riddler
Gender:
Posts: 318


Re: NEW PROBLEM: Factoring 9s
« Reply #25 on: Sep 11^{th}, 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 11^{th}, 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 S_{n} = {10^{1}1, ..., 10^{n}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 n1 distinct remainders available since 0 has been ruled out. Let 10^{j}1, 10^{k}1 be one such pair, with n >= j > k > 0. Then n divides their difference, (10^{j}1)  (10^{k}1) = 10^{j}  10^{k} = (10^{jk}  1)(10^{k}). That is, there exists an integer m such that mn = (10^{jk}  1)(10^{k}). 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 10^{k} 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/10^{k} is an integer, and m'n = 10^{jk}  1. But jk < n, so 10^{jk}  1 is an element of S_{n}. This contradicts our assumption that no such numbers are divisible by n. Therefore there exists an element of S_{n} that is divisible by n.


IP Logged 
http://timmann.org/



Eric Yeh
Senior Riddler
Gender:
Posts: 318


Re: NEW PROBLEM: Factoring 9s
« Reply #27 on: Sep 12^{th}, 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 15^{th}, 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 16^{th}, 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 16^{th}, 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 16^{th}, 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 16^{th}, 2013, 8:58am » 
Quote Modify

on Oct 16^{th}, 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: 7433


Re: Strings of 9s
« Reply #32 on: Oct 16^{th}, 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 12^{th}, 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 



