1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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...