Problem with recursive sequence, sum and divisibility

[VMP]

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 $U_{1}=1+\frac{1}{7}(m-1)$ medals.
On the second day $U_{2}=2+\frac{1}{7}(m-2-U_{1})$ medals, and so on...
On the last day $U_{n}=n$.

Attempt at the solution:

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

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

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

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

Thank you for reading. :)

 

[mfb]

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

More general, you can use the recursion relation to set a condition on U_i-1 based on the knowledge that U_i is an integer.

 

[pat8126]

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 $U_{1}=1+\frac{1}{7}(m-1)$ medals.
On the second day $U_{2}=2+\frac{1}{7}(m-2-U_{1})$ medals, and so on...
On the last day $U_{n}=n$.

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

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)?

 

[VMP]

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)?

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

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

P.S. The condition where $m=-1+13k$ is wrong, same for $n$.

 

[pat8126]

My assumption is: $$U_{i}=i+\frac{1}{7}(m-i-\sum_{j=1}^{i}U_{j}+U_{i})$$

I think the equation should be: $$U_{i}=i+\frac{1}{7}(m-i-\sum_{j=1}^{i-1}U_{j})$$

This gets you the answer: medals = 36, days = 6

 

[VMP]

I think the equation should be: $$U_{i}=i+\frac{1}{7}(m-i-\sum_{j=1}^{i-1}U_{j})$$

This gets you the answer: medals = 36, days = 6

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

Cheers!

 

[pat8126]

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

Cheers!

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?

 

[VMP]

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?

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

Anyhow, here we go:

Solution which should prove uniqueness:

Let $U_{i}$ be defined as following:$$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.$$
For an arbitrary $i>1$ $$U_{i}=\frac{6}{7}(1+U_{(i-1)})$$
if $1+U_{(i)}$ is divisible by 7, then:$$1+U_{(i)}=7q_{i}$$
Since $i$ is arbitrary: $$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$$
After a bit of algebraic manipulation I found this sum: $$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)$$
This condition can only be satisfied iff $q_1=q_i=1\;\; \square$
From which the solutions are easy to find.

Thanks for the help, I tried some programming, but I'm still a bit rusty :)

 

[pat8126]

Thanks for the help, I tried some programming, but I'm still a bit rusty :)

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:

$$U_{n}=\frac{{{6^{n-1}}{m}}+X_{n}} {7^{n}}$$
$$X_{n}={7^n}{6}-{{6^{n-1}}m}$$

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 current 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​

 

[pat8126]

I figured out how to solve for variables m and n with just those three cases.

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

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

You already know the first two values:
$$X_{1}=6$$
$$X_{2}=78$$

Using case n, you know:
$$U_{n}=n$$

As such, you are left with the following equation:
$$n=\frac{{{6^{n-1}}{m}}+X_{n}} {7^{n}}$$Once you substitute the two known values, solve for the two variable equation with the following expressions:
$$7n-m=6$$
$$49n-6m=78$$

As a result, you obtain values:
$$n=6$$
$$m=36$$

With that in mind, you have solved the problem with a closed formula.

 

[mfb]

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.

 

[pat8126]

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.

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.

$${U_{1}}=\frac{m+6}7~~~ {\leftrightarrow} ~~~n=\frac{m+6}{7}~~~{\leftrightarrow}~~~{7n-m}=6$$

$${U_{2}}=\frac{6m+78}{49}~~~ {\leftrightarrow} ~~~n=\frac{6m+78}{49}~~~{\leftrightarrow}~~~{49n-6m}=78$$

Based on those two equations you get values n = 6 and m = 36.

 

[mfb]

Yes, as that appears to be the information from the third condition.

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.

 

[pat8126]

The third condition is just saying something about the last day.

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.

 

[VMP]

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.

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

Cheers!

 

[mfb]

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-U₁ = 0. Subtracting both equations, we get 1+U₁=0.
From the third day, we know that m-3-U₂-U₁ = 0. Subtract the equation from day 2 and we get 1+U₂=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 U_i 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=7². But if we repeat the same exercise with 49x instead of 7x, we see that it has to decrease in steps of 7³ (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.

 

[pat8126]

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!

 

[pat8126]

since $\sum_{j=1}^{n-1}U_{j}=m-n$ It is easy to see that $U_{n}=n$ follows the mentioned pattern.
Cheers!

That was my reasoning as well.

Based on the first two cases, the total previous medals awarded is defined to be $$T=\sum_{k=1}^{n-1}U_{k}$$
The total awards prior to the first day must be 0, as the summation function for n-1 becomes: $$T=\sum_{k=1}^{0}U_{k}$$
When n = n, the equation becomes: $$U_{n}=n$$
which implies that $$U_{n}=n + \frac{1}7{(m-n-T)}$$
with the implicit condition on the last day being $$\frac{1}7{(m-n-T)}=0$$
When n = 1, the equation can be written as: $$U_{1}=n + \frac{1}7{(m-n-T)}$$
When n = 2, the equation can be written as: $$U_{2}=n + \frac{1}7{(m-n-T)}$$
Since the equations are the same, I make them equivalent after plugging in each day's value and obtaining the simplified algebraic form.