wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Number Theory
        
(Message started by: anonymous on Jul 7^th, 2003, 12:10am)

Title: Number Theory
Post by anonymous on Jul 7^th, 2003, 12:10am

Find all positive integers n such that 0,1,...,n-1 can be rearranged into a(0),a(1),...,a(n-1) that satisfied the following condition: the numbers a(0),a(0)a(1),...,a(0)a(1)...a(n-1) give different remainder when divided by n.

Title: Re: Number Theory
Post by towr on Jul 7^th, 2003, 3:56am

on 07/07/03 at 00:10:22, anonymous wrote:

the numbers a(0),a(0)a(1),...,a(0)a(1)...a(n-1)

What's happening here?
I doubt it's multiplication, but concattenation also gives problems for n>10, unless you do the numbers in base n.
I really need a more precise description of what's happening.

Title: Re: Number Theory
Post by wowbagger on Jul 7^th, 2003, 4:10am

on 07/07/03 at 03:56:54, towr wrote:

What's happening here?

I haven't looked into the problem, but the notation used without any further explanation implies multiplication (imho).

Title: Re: Number Theory
Post by towr on Jul 7^th, 2003, 4:16am

Yes, but then the answer is rather trivial, since you can't get different remainders for x and x*1, or x*0 and x*0*a(i)..a(j). So the answer is n=1,2.

Title: Re: Number Theory
Post by wowbagger on Jul 7^th, 2003, 4:49am

on 07/07/03 at 04:16:27, towr wrote:

So the answer is n=1,2.

How about n = 3?
a(j) = (1, 2, 0) works, doesn't it?

Title: Re: Number Theory
Post by towr on Jul 7^th, 2003, 4:56am

hmm.. you're right..
So it just always has to start with 1 and end with 0..

Title: Re: Number Theory
Post by anonymous on Jul 7^th, 2003, 5:10am

Yes, it's multiplication.

This is an old Bulgarian problem. The official problem text can be found on problems.math.umr.edu, but I've forgotten which year.

Title: Re: Number Theory
Post by towr on Jul 7^th, 2003, 5:21am

so far I have

1: [0]
2: [1,0]
3: [1,2,0]
4: [1,3,2,0]
5: [1,2,4,3,0]
7: [1,3,4,6,2,5,0]
11: [1,7,6,4,5,2,3,8,10,9,0]

Title: Re: Number Theory
Post by James Fingas on Jul 7^th, 2003, 7:39am

Hmm...

I think the solution is going to be {1,4,p where p is prime}. I can show that any composite number greater than 4 cannot do this, and I found an easy way to generate the sequence for any prime number. Now I just have to figure out why it works!

Think on this:
13: 1,2,8,10,11,9,12,3,6,4,5,7,0

I also think the question would be more intuitive if we used the numbers 1..N rather than 0..N-1.

UPDATE:
Yes, I think I can show that this method always works. So the numbers this works for are: {1, 4, all prime numbers}

Title: Re: Number Theory
Post by DH on Aug 29^th, 2003, 1:13pm

on 07/07/03 at 07:39:01, James Fingas wrote:

Think on this:
13: 1,2,8,10,11,9,12,3,6,4,5,7,0

I also think the question would be more intuitive if we used the numbers 1..N rather than 0..N-1.

UPDATE:
Yes, I think I can show that this method always works. So the numbers this works for are: {1, 4, all prime numbers}

Yeap ... I found the same method and it's pretty easy to show that it always works.