- #1
PhysicForumz
- 1
- 0
A natural integer N can be written as x mod p, for instance:
N... 1 2 3 4 5 6 7 8 9 10 11 12
p=2 1 2 1 2 1 2 1 2 1 2 1 2
p=3 1 2 3 1 2 3 1 2 3 1 2 3
p=5 1 2 3 4 5 1 2 3 4 5 1 2
p=7 1 2 3 4 5 6 7 1 2 3 4 5
Etc.
The puzzle is quite difficult to state in this format but I'll have a go:
You choose any value x from each row of mod p (up to the maximum value of p, in the above case 7) and eliminate them. You have to find the minumum number N where it is impossible to eliminate all values of N.
Examples:
For p=2, the minimum N is 2. This is because eliminating any value of x (1 or 2), you will always have one remaining.
N... 1 2 3 4 5 6 7 8 9 10 11 12
p=2 1 2For p=3.
N... 1 2 3 4 5 6 7 8 9 10 11 12
p=2 1 2 1
p=3 1 2 3
Having a minimum of N=3 would not work: if you chose x=1 in the p=2 row, you'd eliminate N=1 and N=3. Then you eliminate x=2 in the p=3 row and you eliminate them all.
N... 1 2 3 4 5 6 7 8 9 10 11 12
p=2 1 2 1 2
p=3 1 2 3 1
Having a minimum of N=4 would work however. There is no combination of x you could use to eliminate all values of N. For instance, with x=1 in the p=2 row, you'd eliminate N=1 and N=3. Then whether you choose x=2 or x=1 on the p=3 row, you'd have one left. I.e N=4
For p=5.
N... 1 2 3 4 5 6 7 8 9 10 11 12
p=2 1 2 1 2 1 2
p=3 1 2 3 1 2 3
p=5 1 2 3 4 5 1
I'll leave this to you, but you could try N=6. Try some combinations of x on each row. Is it possible to eliminate every value of N with N=6? (Answer is no :p)
The question is: how do you generalise this up to any p? E.g. how would you find out the minimum N needed when p = 41? What about when p = 211? Etc.
I've had a go, but it gets very tricky after a while trying to eliminate every value of N and finding all the combinations of x to use! I've started to make a program to do this for higher values of p!
Tell me if you need any clarifications / I haven't explained the problem properly
N... 1 2 3 4 5 6 7 8 9 10 11 12
p=2 1 2 1 2 1 2 1 2 1 2 1 2
p=3 1 2 3 1 2 3 1 2 3 1 2 3
p=5 1 2 3 4 5 1 2 3 4 5 1 2
p=7 1 2 3 4 5 6 7 1 2 3 4 5
Etc.
The puzzle is quite difficult to state in this format but I'll have a go:
You choose any value x from each row of mod p (up to the maximum value of p, in the above case 7) and eliminate them. You have to find the minumum number N where it is impossible to eliminate all values of N.
Examples:
For p=2, the minimum N is 2. This is because eliminating any value of x (1 or 2), you will always have one remaining.
N... 1 2 3 4 5 6 7 8 9 10 11 12
p=2 1 2For p=3.
N... 1 2 3 4 5 6 7 8 9 10 11 12
p=2 1 2 1
p=3 1 2 3
Having a minimum of N=3 would not work: if you chose x=1 in the p=2 row, you'd eliminate N=1 and N=3. Then you eliminate x=2 in the p=3 row and you eliminate them all.
N... 1 2 3 4 5 6 7 8 9 10 11 12
p=2 1 2 1 2
p=3 1 2 3 1
Having a minimum of N=4 would work however. There is no combination of x you could use to eliminate all values of N. For instance, with x=1 in the p=2 row, you'd eliminate N=1 and N=3. Then whether you choose x=2 or x=1 on the p=3 row, you'd have one left. I.e N=4
For p=5.
N... 1 2 3 4 5 6 7 8 9 10 11 12
p=2 1 2 1 2 1 2
p=3 1 2 3 1 2 3
p=5 1 2 3 4 5 1
I'll leave this to you, but you could try N=6. Try some combinations of x on each row. Is it possible to eliminate every value of N with N=6? (Answer is no :p)
The question is: how do you generalise this up to any p? E.g. how would you find out the minimum N needed when p = 41? What about when p = 211? Etc.
I've had a go, but it gets very tricky after a while trying to eliminate every value of N and finding all the combinations of x to use! I've started to make a program to do this for higher values of p!
Tell me if you need any clarifications / I haven't explained the problem properly