Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Interesting puzzle I found

  1. Aug 2, 2011 #1
    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 2


    For 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
     
  2. jcsd
  3. Aug 9, 2011 #2
    To rephrase the question, you're asking what is the largest N such that
    [tex]\{1,...,N-1\} \subseteq \bigcup_{j=1}^k(r_j+p_j\mathbb{Z})[/tex] for some values [itex]r_j[/itex] and where [itex]p_j[/itex] is the jth prime number?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Interesting puzzle I found
Loading...