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

Zio (india) problem i don't know how to solve such problems

  1. Jan 26, 2006 #1
    There is a unique sequence of positive numbers that starts with the number 1 at the
    first position and has the following properties.
    • Each value in the sequence is greater than or equal to every value that appears
    earlier in the sequence.
    • If the value at position k in the sequence is m, then the number k appears exactly m times in the sequence.
    The first few numbers in this sequence are
    Position : 1 2 3 4 5 6 7 8 9 10 11 12 · · · Sequence value : 1 2 2 3 3 4 4 4 5 5 5 6 · · ·
    Notice, for instance, that the value at position 4 in the sequence is 3, so 4 itself appears 3 times in the sequence.

    :confused: What is the value that appears at each of the following positions in this sequence?
    (a) 411 (b) 1000 (c) 1245




    -------------Akash
     
  2. jcsd
  3. Jan 26, 2006 #2
    Well, I can certainly find the answer using an excel spreadsheet, but as for an algorithm....? Still working on it.
     
  4. Feb 3, 2006 #3
    I altered the wording of the definition without changing its meaning:

    [itex]a_k[/itex] is a nondecreasing sequence of integers such that [itex]a_1 = 1[/itex] and has the following property. If the value at position k in the sequence is m, then the number k appears exactly m times in the sequence.

    What are the following values?

    (a) [itex]a_{411}[/itex]
    (b) [itex]a_{1000}[/itex]
    (c) [itex]a_{1245}[/itex]

    I was unable to come up with a closed form for the solution. The three values required are:


    (a) [itex]a_{411}[/itex] = 50
    (b) [itex]a_{1000}[/itex] = 86
    (c) [itex]a_{1245}[/itex] = 98

    I found these by brute force.
     
    Last edited: Feb 3, 2006
  5. Feb 3, 2006 #4
    One stipulation: [itex]a_2 = 2[/itex]. Otherwise, [itex]a_2[/itex] could be anything.

    As for solving it, I couldn't get anything either for the Nth case, or even really an iterative case. Interestingly, I think the problem may be intended to inspire a slight trick on a brute force technique, thanks to the choosing of the number 1245.

    If you draw out the sequence, you can predict what a number at a later position will be. Suppose you have f(n) such that f(n) = f(n-1) + [itex]a_n[/itex]. We draw a little chart of N, [itex]a_n[/itex], and f(n):

    n, [itex]a_n[/itex], f(n)

    Hence, you get a little chart, wherein n will be in the series from position f(n-1)+1 to f(n).

    1, 1, 1
    2, 2, 3
    3, 2, 5
    4, 3, 8
    5, 3, 11
    6, 4, 15
    7, 4, 19
    8, 4, 23
    (etc)

    Translation:
    The number 6 will be between (11+1)th through the 15th position.
    The number 7 will be between (15+1)th through the 19th position.
    The number 8 will be between (19+1)th through the 23rd position.
    Etc.

    The interesting thing being that if you write the series itself until you complete the number 20 (at n=98), you discover that 98 is between positions 1227 and 1246 in the series. Since 20 is a pretty round number, it looks like it might have been done this way, seeing as 1245 is one number short of 1246.

    DaveE
     
  6. Feb 3, 2006 #5
    Not so. If [itex]a_2 = m, m > 2[/itex], then 2 would have to appear m times and so the sequence would not be nondecreasing.
     
  7. Feb 3, 2006 #6
    Oh yeah! (oops) Ok, forget I said that.

    DaveE
     
  8. Feb 9, 2006 #7
    1
    22 33
    444 555
    6666 7777
    88888 99999........


    It seems like a pretty predictable pattern.
     
    Last edited: Feb 9, 2006
  9. Feb 10, 2006 #8
    Not quite-- slight mistake above: there should be four 8's, not 5, which puts them on the previous line of the way you're drawing the pattern. Drawing the pattern the way you're drawing it, you can do something like (base 36 shown):

    1
    22 33
    444 555
    6666 7777 8888
    99999 AAAAA BBBBB
    CCCCCC DDDDDD EEEEEE FFFFFF
    GGGGGGG HHHHHHH IIIIIII JJJJJJJ
    KKKKKKKK LLLLLLLL MMMMMMMM NNNNNNNN
    OOOOOOOOO PPPPPPPPP QQQQQQQQQ RRRRRRRRR SSSSSSSSS
    TTTTTTTTTT UUUUUUUUUU VVVVVVVVVV WWWWWWWWWW XXXXXXXXXX

    Note that each line contains the number of groups equal to the next number in the sequence. Hence, the 1st line has 1, then 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, etc.

    DaveE
     
  10. Feb 26, 2006 #9
    still, the pattern seem simple enough. If only i had the patience....
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Zio (india) problem i don't know how to solve such problems
  1. How to solve a problem (Replies: 22)

  2. I don't know how. (Replies: 5)

Loading...