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!

I Problem with recursive sequence, sum and divisibility

  1. Oct 8, 2016 #1

    VMP

    User Avatar

    Hello everyone, I have an issue solving the following problem:

    You're on a mathematical Olympiad, there are m medals and it lasts for n days.
    First day committee gives [itex]U_{1}=1+\frac{1}{7}(m-1)[/itex] medals.
    On the second day [itex]U_{2}=2+\frac{1}{7}(m-2-U_{1})[/itex] medals, and so on...
    On the last day [itex]U_{n}=n[/itex].

    Attempt at the solution:

    My assumption is: [tex]U_{i}=i+\frac{1}{7}(m-i-\sum_{j=1}^{i}U_{j}+U_{i})[/tex]
    If i take the difference of [itex]U_{i}-U_{(i-1)}[/itex],
    I find this way to write the recursion:[tex]U_{i}=\frac{6}{7}(1+U_{(i-1)}),\;(i=2,3,...,n)[/tex]

    If I set [itex]i=n[/itex] and do some algebra, then I get the following:[tex]13n=6+6m\;\; (1)[/tex]

    ...and this is where I'm not sure what to do, number of medals must be discrete...
    Every [itex]U_{i}[/itex] must be discrete.

    I tried from equation (1) to derive what m and n must be:[tex]n=6k \\ m=-1+13k,\;k\epsilon \mathbb{N}[/tex] However I am not sure how to capture this notion that every [itex]U_{i}[/itex] must be discrete.

    Thank you for reading. :)
     
  2. jcsd
  3. Oct 8, 2016 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Did you plug in your m into the formula for U1 and see what you get? This gives an additional condition.

    More general, you can use the recursion relation to set a condition on Ui-1 based on the knowledge that Ui is an integer.
     
  4. Oct 8, 2016 #3
    So are you trying to find a solution to (m, n) such that there's an award of a certain amount of medals each day, that is an integer by definition, and the sum of medals given on days 1 to n will equal m?

    While the numbers don't work out relative to your above equation, are you saying something like: Day 1 there's an award of 1 medal, day 2 there's an award of 2 medals, day 3 there's an award of 3 medals for a total (m, n) = (6, 3)?
     
  5. Oct 9, 2016 #4

    VMP

    User Avatar

    Let's say [itex]m=8[/itex] then the number of medals given on day 1 is [itex]U_{1}=2[/itex]

    Problem is to find an elegant condition for [itex]U_{i}[/itex] such that every [itex]U_{i}\epsilon\mathbb{N},\forall i,(i=1,2,...,n)[/itex].

    P.S. The condition where [itex]m=-1+13k[/itex] is wrong, same for [itex]n[/itex].
     
    Last edited: Oct 9, 2016
  6. Oct 9, 2016 #5
    I think the equation should be: [tex]U_{i}=i+\frac{1}{7}(m-i-\sum_{j=1}^{i-1}U_{j})[/tex]

    This gets you the answer: medals = 36, days = 6
     
  7. Oct 9, 2016 #6

    VMP

    User Avatar

    Note that if [itex]i=1[/itex] the sum is undefined. Did you guess the answer or do you have a systematic approach?

    Cheers!
     
  8. Oct 9, 2016 #7
    Concerning i = 1, I don't believe that it's undefined. When the lower bound is greater than the upper bound, the summation function should equal 0 by convention, which represents the first day's expression.

    As for the solution, I just ran a few lines of code that I programmed. I could try and formulate a simplified equation, though it might take a few hours. Are you looking for the equation that avoids the sigma notation?
     
  9. Oct 9, 2016 #8

    VMP

    User Avatar

    Interesting, it's a good convention in that context.

    Anyhow, here we go:

    Solution which should prove uniqueness:

    Let [itex]U_{i}[/itex] be defined as following:[tex]
    U_{i}=\left\{\begin{matrix}
    1+\frac{1}{7}(m-1),\;i=1\\\\
    U_{i}=\frac{6}{7}(1+U_{(i-1)}),\;i=2,...,n
    \end{matrix}\right.
    [/tex]
    For an arbitrary [itex]i>1[/itex] [tex]U_{i}=\frac{6}{7}(1+U_{(i-1)})[/tex]
    if [itex]1+U_{(i)}[/itex] is divisible by 7, then:[tex]1+U_{(i)}=7q_{i}[/tex]
    Since [itex]i[/itex] is arbitrary: [tex]U_{i}+1=7q_{i}\\7q_{2}=6q_{1}+1\\7q_{3}=6q_{2}+1\\.........\\7q_{i+1}=6q_{i}+1\\..........\\7q_{n}=6q_{n-1}+1[/tex]
    After a bit of algebraic manipulation I found this sum: [tex]q_{i}=\frac{6^{i-1}}{7^{i-1}}(q_{1}-1)+\sum_{j=1}^{i-1}\frac{6^{j-1}}{7^{j}}\\\\(condition)\;\;q_{i}-1=\frac{6^{i-1}}{7^{i-1}}(q_1-1)[/tex]
    This condition can only be satisfied iff [itex]q_1=q_i=1\;\; \square [/itex]
    From which the solutions are easy to find.

    Thanks for the help, I tried some programming, but I'm still a bit rusty :)
     
  10. Oct 9, 2016 #9
    I'm glad that I could help you out!

    By the way, I came up with this formula when plugging and chugging with value m = 36:

    [tex]U_{n}=\frac{{{6^{n-1}}{m}}+X_{n}} {7^{n}}[/tex]
    [tex]X_{n}={7^n}{6}-{{6^{n-1}}m}[/tex]

    As you can see, it simply reduces to 6 each time. I'm not sure how to find the solution (m, n) without brute force.

    As for the computer code, I wrote a snippet in VBA as follows:

    'loop though all possible medal total counts
    'must be at least 8 total medals for day 1 to be integer
    For m = 8 To 5000
    'keep awarding medals on daily basis until reach curent m
    n = 1
    awardsGiven = 0
    currentDayAwards = 0
    itWorks = False

    While awardsGiven < m
    currentDayAward = n + ((1 / 7) * (m - n - awardsGiven))

    'make sure it's an integer; if not, then selected m does not work
    temp = Int(currentDayAward)
    If temp <> currentDayAward Then
    awardsGiven = m
    itWorks = False​
    Else
    awardsGiven = awardsGiven + currentDayAward
    itWorks = True
    n = n + 1​
    End If​
    Wend

    If itWorks = True Then MsgBox ("m = " + Str(m) + "... n = " + Str(n))

    Next m​
     
    Last edited: Oct 9, 2016
  11. Oct 9, 2016 #10
    I figured out how to solve for variables m and n with just those three cases.

    First, simplify both cases:
    [tex]U_{1}=\frac{m+6} {7}[/tex]
    [tex]U_{2}=\frac{6m+78}{49}[/tex]

    Based on that, you can see a pattern that emerges:
    [tex]U_{n}=\frac{{{6^{n-1}}{m}}+X_{n}} {7^{n}}[/tex]

    You already know the first two values:
    [tex]X_{1}=6[/tex]
    [tex]X_{2}=78[/tex]

    Using case n, you know:
    [tex]U_{n}=n[/tex]

    As such, you are left with the following equation:
    [tex]n=\frac{{{6^{n-1}}{m}}+X_{n}} {7^{n}}[/tex]


    Once you substitute the two known values, solve for the two variable equation with the following expressions:
    [tex]7n-m=6[/tex]
    [tex]49n-6m=78[/tex]

    As a result, you obtain values:
    [tex]n=6[/tex]
    [tex]m=36[/tex]

    With that in mind, you have solved the problem with a closed formula.
     
  12. Oct 10, 2016 #11

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Are you assuming that all days get the same number of medals here? Otherwise I don't see how you get the equations that depend on m and n only.
     
  13. Oct 10, 2016 #12
    Yes, as that appears to be the information from the third condition.

    In retrospect, you don't need to go any further than simplifying the first two cases and solving a set of two linear equations. The simplification process does not involve the knowledge of either variable, as it's just algebraic manipulation.

    [tex]{U_{1}}=\frac{m+6}7~~~ {\leftrightarrow} ~~~n=\frac{m+6}{7}~~~{\leftrightarrow}~~~{7n-m}=6[/tex]

    [tex]{U_{2}}=\frac{6m+78}{49}~~~ {\leftrightarrow} ~~~n=\frac{6m+78}{49}~~~{\leftrightarrow}~~~{49n-6m}=78[/tex]

    Based on those two equations you get values n = 6 and m = 36.
     
    Last edited: Oct 10, 2016
  14. Oct 10, 2016 #13

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    The third condition is just saying something about the last day. From the description I'm not even sure if it has to follow the pattern of the previous days.
     
  15. Oct 10, 2016 #14
    Yes, that is what I thought as well.

    Based on the simplicity of the solution that I posted, there seems to be two possibilities. Either (1) the wording of the problem was not clear or (2) such an assumption is merely a correct guess to a problem that requires a different general solution involving summation.

    Since there's an equivalent function for days one and two, with day one having zero previous medals awarded, the last function should equal the first and second function. As such, I would just indicate that the functions for the first two days are equivalent to day n, hence the equivalence operation placing n on the left side.

    If you believe it's the latter, then I'm still unsure how to solve it properly.
     
    Last edited: Oct 10, 2016
  16. Oct 10, 2016 #15

    VMP

    User Avatar

    If for the i-th day day [tex]U_{i}=i+\frac{1}{7}(m-i-\sum_{j=1}^{i-1}U_{j})[/tex] then [tex]U_{n}=n+\frac{1}{7}(m-n-\sum_{j=1}^{n-1}U_{j})[/tex]
    since [itex]\sum_{j=1}^{n-1}U_{j}=m-n[/itex] It is easy to see that [itex]U_{n}=n[/itex] follows the mentioned pattern.
    I've already checked the result in the beginning but forgot to mention it.

    Cheers!
     
  17. Oct 10, 2016 #16

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Good observation with day n.

    It is not necessary to make any assumptions.

    m=1, n=1 is a trivial solution - one that has not been mentioned so far. To look for further solutions, assume n>1.

    $$U_{k}=k+\frac{1}{7}(m-k-\sum_i=1^{k-1} U_i)$$

    Now consider everything mod 7:
    From the first day we know that m-1=0 (m-1 has to be divisible by 7). m=8 does not work therefore there are at least 15 medals involved. It is easy to see that we need at least 4 days, so the first three days follow the described equation.
    From the second day we know that m-2-U1 = 0. Subtracting both equations, we get 1+U1=0.
    From the third day, we know that m-3-U2-U1 = 0. Subtract the equation from day 2 and we get 1+U2=0. This pattern continues for all days following this formula. Therefore, all days give out a number of medals which has remainder 6 if divided by 7.

    Back to absolute numbers:
    It is easy to see that##U_{i+1} \leq U_i + 1##. Combine this with the remainder condition from above (differences are multiples of 7) and we see that Ui cannot increase.

    To decrease by 7x with x>0, we get the condition
    ##7x + k+\frac{1}{7}(m-k-\sum_i=1^{k-1} U_i) = k-1+\frac{1}{7}(m-(k-1)-\sum_i=1^{k-2} U_i)##
    Simplify:
    ##49x + 6 - U_{k-1} = 0##. Which means we get the stronger condition ##U_{k}=6 mod 49## for all days apart from the last two. If the number of medals is decreasing, it has to decrease in steps of 49=72. But if we repeat the same exercise with 49x instead of 7x, we see that it has to decrease in steps of 73 (apart from the last three days), and so on. This does not work. No matter how we start, if the number of medals is decreasing we run into non-integers after at most log(m)/log(7) steps, which is smaller than n (=the day that saves us by breaking the pattern) for all m that have not been ruled out so far.

    Therefore, the only option is a constant number of medals per day (apart from possibly the last day). And with that assumption we quickly see that handing out 6 medals each day is the only option.

    Note that there are values of m which lead to integer medals for the first i days for every i. As an example, starting with 379 medals leads to 55 medals on day 1, 48 medals on day 2 (note the decrease by 7) and 42 medals on day 3. 42+1 is not divisible by 7 any more so afterwards we get non-integers.
     
  18. Oct 10, 2016 #17
    Thank you so much for helping us tackle this problem, mfb. I truly appreciate it. It's been over a decade since I studied discrete algorithms, so I'm extremely rusty.

    Also, good catch with (1,1) - smart!
     
    Last edited: Oct 10, 2016
  19. Oct 10, 2016 #18
    That was my reasoning as well.

    Based on the first two cases, the total previous medals awarded is defined to be [tex]T=\sum_{k=1}^{n-1}U_{k}[/tex]
    The total awards prior to the first day must be 0, as the summation function for n-1 becomes: [tex]T=\sum_{k=1}^{0}U_{k}[/tex]
    When n = n, the equation becomes: [tex]U_{n}=n[/tex]
    which implies that [tex]U_{n}=n + \frac{1}7{(m-n-T)}[/tex]
    with the implicit condition on the last day being [tex]\frac{1}7{(m-n-T)}=0[/tex]
    When n = 1, the equation can be written as: [tex]U_{1}=n + \frac{1}7{(m-n-T)}[/tex]
    When n = 2, the equation can be written as: [tex]U_{2}=n + \frac{1}7{(m-n-T)}[/tex]
    Since the equations are the same, I make them equivalent after plugging in each day's value and obtaining the simplified algebraic form.
     
    Last edited: Oct 10, 2016
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Problem with recursive sequence, sum and divisibility
  1. Sequence Sum (Replies: 4)

Loading...