Home Page Forums Puzzles Divisor puzzle

Tagged: ,

  • Divisor puzzle

     Vivek updated 3 months, 1 week ago 2 Members · 13 Posts
  • James

    Member
    March 4, 2021 at 1:09 am

    Here’s an interesting puzzle that you can do with a pack of cards. Start with the cards 1, 2, …, N, where N is some whole number. If you’re doing this with cards, then you might count the Jack as 11, the Queen as 12, King as 13. Let’s say, for purposes of this example, that N=5, so you start with the Ace, 2, 3, 4 and 5 of diamonds (Ace being 1). The aim of the puzzle is to play all the cards to the table obeying the following rules:

    1. The first card played must be the highest card, the 5 of diamonds in this case.
    2. Subsequent cards can only be played if they are a divisor of the cumulative total of the cards currently on the table. A divisor is a smaller number that evenly divides a larger number.

    In the present example, a valid sequence of plays would be 5 (5), A (6), 2 (8), 4 (12), 3 (15), where I’ve put the cumulative total in brackets afterwards.

    It gets progressively harder as N gets larger. Also, for N>13 you tend to run out of cards, so you have to do it in your head! I got up to N=23. How high can you go? Maybe post your solutions below so that we can compare.

  • Vivek

    Member
    March 4, 2021 at 4:01 pm

    Hi James, This is a very interesting problem. I try to write a program for it. By the by, If you find the sequence for 23, then from that we can find the sequence for 24, Right? For example, Suppose the sequence for N=P, where P is prime, is as follows :- P,1,a1,a2,…,ak. Then, The sequence for N=P+1, is :- P+1,a1,a2,…,ak,P, 1.

    Like When N=5 :- 5,1,2,4,3

    So, When N=6:- 6,2,4,3,5,1

  • Vivek

    Member
    March 4, 2021 at 6:04 pm

    There are 4 solutions, When N=13. There are 372 different solutions when N=23. And When N=30, There are 32367 solutions!!! Here is the pure brute force program in C : https://drive.google.com/file/d/1R2qgYarQkqO5CfXcGfw0poyHNZi4ka3Y/

    This program is not efficient though. Even When N=51, The computer takes few minutes to churn out the solutions…

    • Vivek

      Member
      March 4, 2021 at 6:17 pm

      few solutions for N=51…

  • James

    Member
    March 5, 2021 at 1:49 am

    That’s a very neat observation about p, p+1! I like it. I came up with this puzzle last year during lockdown whilst trying to design a maze using divisors. I got quite excited for a bit and also wrote a program to work out the number of solutions for each N. Out of curiosity, I put the resulting sequence into the Online Encyclopedia of Integer Sequences and found that it was already a ‘thing’. I don’t know if it’s been proved that a solution exists for all N.

    I like the puzzle because it’s relaxing to sit there with a pack of cards and try to figure it out. It’s a great patience game.

    • Vivek

      Member
      March 5, 2021 at 2:30 pm

      I always wonder at the creativity level of the puzzle creators, James !! Yeah, This one is really a good puzzle. I too wonder whether the solution is possible for all N. It would be awesome If we could come up with some proof.

    • James

      Member
      March 6, 2021 at 1:38 am

      I think a general proof is well beyond my capabilities. It’d be great if someone could prove it for all N. It certainly looks like the number of solutions is generally increasing with N, but I know that there have been quite a few conjectures that don’t hit a counter example until absurdly high numbers.

      I came up with two divisor mazes off the back of that problem. The first one is at http://www.webmazes.net/divisorMaze1.

    • Vivek

      Member
      March 6, 2021 at 3:22 pm

      James, Got it 😀 The proof is easy and the sequence can be generated with simple rules for every N. Before We noted the cases for N=P and N=P+1. Initially we said P is the prime. But It can be any odd number as sum of first n natural number is divided by n, if n is odd. So, If we can get the sequence for the odd number, then from that the sequence of the next even number can be generated.

      Now The rules to create the sequence for odd numbers is as follows :-

      Suppose N=2m+1.

      Then, a1=2m+1, a2=1.

      a(2k)=m+k , for all 2<=k<=m

      a(2k+1)=k+1, for all 1<=k<=m

      This is it. This will generate our sequence. It is easy to note that a2 divides a1.

      Also, It is easy to prove that

      S(2k)=(m+k)(k+1), for all 1<=k<=m

      S(2k+1)=(m+k+1)(k+1) , for all 1<=k<=m

      From this, We can see a(2k+1) divides S(2k) and a(2k+2) divides S(2k+1).

      The easy way to form the sequence is as follows:-

      Consider the case when N=13.

      We start with 13,1,2 subsequently we write consecutive numbers 3,4,5 and so on till (13+1)/2 that is 7 with single gap between the terms. After that winding up to the first gap, we continue filling the gaps with consecutive numbers 8,9,10 and so on, till all the gaps are filled.

      Step 1: 13 , 1 , 2 , x , 3 , x , 4 , x , 5 , x , 6 , x , 7

      Step 2: 13 , 1 , 2 , 8 , 3 , 9 , 4 , 10 , 5 , 11 , 6 , 12 , 7

      That is it :D.

      To form the sequence for 14, We just replace 13 , 1 with 14 and append 13 , 1 at the end.

      14 , 2 , 8 , 3 , 9 , 4 , 10 , 5 , 11 , 6 , 12 , 7 , 13 , 1

      Another way to form the same sequence:

      a1=2m+1

      a2=1

      a3=2

      ak = S(k-1)/a(k-1) , for all 4<=k<=2m+1

  • James

    Member
    March 6, 2021 at 4:15 pm

    That’s superb. I’m so impressed you managed to work it out. I will work through it on paper later (I’m a physicist by trade, so not super hot on proving stuff!). Great work.

  • James

    Member
    March 6, 2021 at 4:16 pm

    I’ve attempted to read G.H. Hardy’s book on number theory several times but with only mixed success!

    • Vivek

      Member
      March 6, 2021 at 9:48 pm

      I too love to learn number theory deeply, James. I got some introduction to number theory from the Discrete Math book by Kenneth Rosen. Also “A friendly introduction to number theory” by Joseph Silverman, is one nice book.

  • James

    Member
    March 6, 2021 at 4:42 pm

    I’ve worked through it and it looks good to me. I can’t get over how cool that proof is. You should think about publishing it (if it’s not already known). I can’t remember which sequence it was on the OEIS, but I can try to find out again, if that’s any use to you?

    • Vivek

      Member
      March 6, 2021 at 9:57 pm

      James, I accidentally noted the pattern of consecutive numbers in the sequences. And checked whether the same pattern could work for any N and it did 🙂 I think the proof is not profound.

      Creating puzzles like this, opens up lots of interesting stuffs. Keep doing that. Will have an eye on your site… 🙂

Log in to reply.

Original Post
0 of 0 posts June 2018
Now