Author |
Topic: Number Theory (Read 806 times) |
|
anonymous
Guest
|
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: 
Posts: 13730
|
 |
Re: Number Theory
« Reply #1 on: Jul 7th, 2003, 3:56am » |
 Quote  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
 
Gender:
Posts: 727
|
|
Re: Number Theory
« Reply #2 on: Jul 7th, 2003, 4:10am » |
Quote Modify
|
on Jul 7th, 2003, 3:56am, towr wrote:
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:
Posts: 13730
|
|
Re: Number Theory
« Reply #3 on: Jul 7th, 2003, 4:16am » |
Quote 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
Gender:
Posts: 727
|
|
Re: Number Theory
« Reply #4 on: Jul 7th, 2003, 4:49am » |
Quote Modify
|
on Jul 7th, 2003, 4:16am, towr wrote:
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:
Posts: 13730
|
|
Re: Number Theory
« Reply #5 on: Jul 7th, 2003, 4:56am » |
Quote 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
|
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:
Posts: 13730
|
|
Re: Number Theory
« Reply #7 on: Jul 7th, 2003, 5:21am » |
Quote 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
Gender:
Posts: 949
|
|
Re: Number Theory
« Reply #8 on: Jul 7th, 2003, 7:39am » |
Quote 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
|
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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove