wu :: forums
« wu :: forums - Number Theory »

Welcome, Guest. Please Login or Register.
Mar 28th, 2024, 8:08am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: towr, william wu, Icarus, SMQ, Grimbal, Eigenray)
   Number Theory
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Number Theory  (Read 789 times)
anonymous
Guest

Email

Number Theory  
« on: Jul 7th, 2003, 12:10am »
Quote Quote Modify Modify Remove Remove

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.
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Number Theory  
« Reply #1 on: Jul 7th, 2003, 3:56am »
Quote Quote Modify Modify

on Jul 7th, 2003, 12:10am, 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.
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
wowbagger
Uberpuzzler
*****





242002184 242002184    


Gender: male
Posts: 727
Re: Number Theory  
« Reply #2 on: Jul 7th, 2003, 4:10am »
Quote Quote Modify Modify

on Jul 7th, 2003, 3:56am, towr wrote:
What's happening here?

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

"You're a jerk, <your surname>!"
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Number Theory  
« Reply #3 on: Jul 7th, 2003, 4:16am »
Quote Quote Modify Modify

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.
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
wowbagger
Uberpuzzler
*****





242002184 242002184    


Gender: male
Posts: 727
Re: Number Theory  
« Reply #4 on: Jul 7th, 2003, 4:49am »
Quote Quote Modify Modify

on Jul 7th, 2003, 4:16am, towr wrote:
So the answer is n=1,2.

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

"You're a jerk, <your surname>!"
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Number Theory  
« Reply #5 on: Jul 7th, 2003, 4:56am »
Quote Quote Modify Modify

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

Wikipedia, Google, Mathworld, Integer sequence DB
anonymous
Guest

Email

Re: Number Theory  
« Reply #6 on: Jul 7th, 2003, 5:10am »
Quote Quote Modify Modify Remove Remove

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.
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Number Theory  
« Reply #7 on: Jul 7th, 2003, 5:21am »
Quote Quote Modify Modify

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]
 
« Last Edit: Jul 7th, 2003, 7:05am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: Number Theory  
« Reply #8 on: Jul 7th, 2003, 7:39am »
Quote Quote Modify Modify

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}
« Last Edit: Jul 7th, 2003, 8:22am by James Fingas » IP Logged

Doc, I'm addicted to advice! What should I do?
DH
Guest

Email

Re: Number Theory  
« Reply #9 on: Aug 29th, 2003, 1:13pm »
Quote Quote Modify Modify Remove Remove

on Jul 7th, 2003, 7:39am, 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.
IP Logged
Pages: 1  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