# Basic Math Challenge - July 2018

• Challenge
• Featured
Mentor

## Main Question or Discussion Point

Summer is coming and brings a new basic math challenge! Enjoy! For more advanced problems you can check our other intermediate level math challenge thread!

RULES:
1) In order for a solution to count, a full derivation or proof must be given. Answers with no proof will be ignored. Solutions will be posted around 15th of the following month.
2) It is fine to use nontrivial results without proof as long as you cite them and as long as it is "common knowledge to all mathematicians". Whether the latter is satisfied will be decided on a case-by-case basis.
3) If you have seen the problem before and remember the solution, you cannot participate in the solution to that problem.
4) You are allowed to use google, wolframalpha or any other resource. However, you are not allowed to search the question directly. So if the question was to solve an integral, you are allowed to obtain numerical answers from software, you are allowed to search for useful integration techniques, but you cannot type in the integral in wolframalpha to see its solution.
5) Mentors, advisors and homework helpers are kindly requested not to post solutions, not even in spoiler tags, for the challenge problems, until 16th of each month. This gives the opportunity to other people including but not limited to students to feel more comfortable in dealing with / solving the challenge problems. In case of an inadvertent posting of a solution the post will be deleted by @fresh_42

QUESTIONS:
1. (solved by @Mr Davis 97 ) Show that ##\arctan \sqrt \frac{1 - x}{1 + x} + \frac{1}{2} \arcsin x = \frac{\pi}{4}##, for all ##x \in (-1, 1)## (by @QuantumQuest)

2. (solved by @mfb ) You want to drive a car around a one way circular track. The car uses a constant amount of diesel per mile driven. There are N diesel canisters mischievously placed around the track. Summing over all gas canisters there is enough fuel to make one full trip /cycle around the track. Your car initially has no gas. Does there always exist a starting position (i.e. at one of the N gas canisters) that you may choose such that you can complete one full trip around the track? (by @StoneTemplePython)

3. (solved by @ehild ) The angle bisector in a given triangle ##\bigtriangleup ABC## of the angle ##\alpha = \sphericalangle BAC## at ##A## intersects the side ##\overline{BC}## at the point ##D##. We have the information:
\begin{align*}
\end{align*}
a) Determine the inner angles of ##\bigtriangleup ABC##.
b) Determine the precise ratio at which ##D## divides ##\overline{BC}##
(by @fresh_42)

4. (solved by @ehild ) The beam from a lighthouse ##3## miles from a straight coastline turns at the rate of ##5## revolutions per minute. How fast is the point ##P## at which the beam hits the shore moving when that point is ##4## miles from point ##A## on the shore directly opposite the lighthouse? (by @QuantumQuest)

5. (solved by @Mr Davis 97 ) Compute the arc length ##\mathcal{L}## of the cycloid
$$\gamma\, : \,\mathbb{R} \longrightarrow \mathbb{R}^2\, , \,\gamma(t)=(t-\sin(t),1-\cos(t))$$
between two neighboring singularities. (by @fresh_42)

6. (solved by @Mr Davis 97 )Let ##a## be an integer and ##b## be also an integer which is formed from ##a## by reversing the order of its digits.
Show that ##a \equiv b \mod 9\,##. (by @QuantumQuest)

7. An urn contains balls, each of which has one of the following colors: red, green, blue and yellow balls. Balls are sampled randomly with replacement. Let r, g, b, and y represent the probabilities of drawing a red, green, blue or yellow.

a) (solved by @Math_QED ) what is the expected number of balls chosen before obtaining the first yellow ball?
b) (solved by @PeroK ) what is the expected number of different colors of balls obtained before getting the first yellow ball?
(by @StoneTemplePython)

8. Let ##f## be a differentiable function in ##\mathbb{R}##. If ##f'## is invertible and ##(f')^{-1}## is differentiable in ##\mathbb{R}##, show that ##[I_A (f')^{-1} - f \circ [(f')^{-1} ]]' = (f')^{-1}## where ##I_A## with ##I_A(x) = x## is the identity function ##I_A : A \to A##
(by @QuantumQuest)

9. (solved by @lpetrich ) At the cash desk of a shopping center five friends (Diana, Ike, Jessica, Stan, Valery) are standing in a row. They are all different in age (26, 27, 30, 33 and 35 years) and would like to buy all different tops (shirt, polo shirt, pullover, sweatshirt and T-shirt) for themselves. The tops are all different colors (blue, yellow, green, red and black) and different sizes (XS, S, M, L and XL).

Find out who is where, how old and what top to buy in which color and size. The positions in the queue can be seen from the cashier, i.e. "front" or "the first person" is right at the cash register. There are no other people in the queue and the cashier is to be ignored.

A. Diana, who wants to buy a top in size XL, stands further ahead than the person who wants to buy a black top.
B. Jessica stands in front of the person who wants to buy a polo shirt.
C. The second person in the queue wants to buy a yellow top.
D. The t-shirt is not red.
E. Stan wants to buy a sweatshirt. The person standing in front of him is older than the person standing directly behind him.
F. Ike needs a top in size L.
G. The last person in the queue is 30 years old.
H. The oldest person wants to buy the top in the smallest size.
I. The person standing directly behind Valery wants to buy a red top that is larger than size S.
J. The youngest person wants to buy a yellow top.
K. Jessica wants to buy a shirt.
L. The third person in the queue wants to buy a top in size M.
M. The polo shirt is red, yellow or green.
(by @fresh_42)

10. (solved by @lpetrich ) Suppose we have two ##\text{ n x n }## commuting matrices, ##\mathbf X## and ##\mathbf Y##.

##\mathbf X## is special because there exists some positive integer ##k## where ##\mathbf X^k = \mathbf I##. On the other hand, ##\mathbf Y## is nilpotent.
a) Prove that ##\mathbf Z := \big(\mathbf X + \mathbf Y\big)## is nonsingular, and
b) compute the ##\mathbf Z^{-1}##.
(by @StoneTemplePython)

Last edited:
• ISamson, Mr Davis 97, Amrator and 3 others

No. It isn't.
Here is my logic.
Rate of usage: 1l of diesel per mile.
Let the number of canisters be 'N.'
However, all the canisters spread around the track aren't of equal capacity, as it isn't mentioned otherwise in the question.
Let: The track be of 100 miles. There are 2 canisters overall. One of 1l diesel and other of 99litres of diesel.
It isn't mentioned that the can containing 99litres of diesel WILL be at the starting of 2nd mile (when fuel of 1st can is exhausted). All that is mentioned is that the ∑Fuel spread over the track is 100 litres.
But, the fuel can of 99l diesel might be kept at not a point where 1 litre diesel gets finished, for example, at 5th mile. 3 miles away from the stopped car.

(Note: The only possibility of the driver completing the circuit is when the cans of x litres are kept at a distance of x miles from each other. The value of x is variable for every checkpoint or everytime the driver picks up a can. For eg, if a driver picks up a can of 5litres diesel, the next can MUST be kept at 5 miles away.)
Thank you.

StoneTemplePython
Gold Member
2019 Award
Let: The track be of 100 miles. There are 2 canisters overall. One of 1l diesel and other of 99litres of diesel.
It isn't mentioned that the can containing 99litres of diesel WILL be at the starting of 2nd mile (when fuel of 1st can is exhausted).
I'd suggest carefully re-reading the question. It in fact says

Your car initially has no gas. Does there always exist a starting position (i.e. at one of the N gas canisters) that you may choose such that you can complete one full trip around the track?

• scottdave
Here is my solution to question 1:

First, we focus on simplifying the expression ##\displaystyle \arctan \sqrt \frac{1 - x}{1 + x}##. Let ##x = \cos 2 t##. Then ##\displaystyle \arctan \sqrt \frac{1 - \cos 2t}{1 + \cos 2t} = \arctan \sqrt \frac{2 \sin^2 t}{2 \cos^2 t} = \arctan |\tan t |##. Since ##x \in (-1,1)##, we know ##t \in (0, \pi /2)##, so ##\tan t > 0## and we can drop the absolute value. So ultimately, we have that ##\displaystyle \arctan \sqrt \frac{1 - x}{1 + x} = t = \frac{1}{2} \arccos x##. Now, ##\displaystyle \frac{1}{2} \arcsin x + \frac{1}{2} \arccos x = \frac{1}{2} (\arcsin x + \arccos x)##. But by the cofunction identities ##\sin (\pi / 2 - \theta) = \cos \theta \implies \sin (\pi / 2 - \arccos x ) = x \implies \pi / 2 - \arccos x = \arcsin x \implies \arcsin x + \arccos x = \pi / 2## as long as ##x \in (-1, 1)##.
So we have our final answer, ##\displaystyle \frac{1}{2} \cdot \frac{\pi}{2} = \frac{\pi}{4}##.

Last edited:
• QuantumQuest
Here is my solution to question 5:

Every singularity occurs at ##t = 2 \pi n## where ##n \in \mathbb{Z}##. We will compute the arc length from ##0## to ##2 \pi##. From multivariable calculus, we know that when a curve is defined parametrically the arc length along the curve as ##t## varies from ##a## to ##b## is ##\displaystyle \int_a^b \sqrt{\left( \frac{dx}{dt}\right)^2 + \left( \frac{dy}{dt} \right)^2} ~ dt##. Substituting the information we have on hand results in the following integral: ##\displaystyle \int_0^{2 \pi} \sqrt{(1-\cos t)^2 + ( \sin t)^2} ~ dt = \int_0^{2 \pi} \sqrt{2 - 2 \cos t} ~ dt = \sqrt{2} \int_0^{2 \pi} \sqrt{1 - \cos t} ~ dt##. By symmetry of the integrand, we have the equivalent integral ##\displaystyle 2 \sqrt{2} \int_0^{\pi} \sqrt{1 - \cos t} ~ dt##. Note that ##\displaystyle 2 \sin^2 (\frac{t}{2}) = 1 - \cos t##, so we merely have to evaluate ##\displaystyle 4 \int_0^{\pi} \sin \frac{t}{2} ~ dt##, which is equal to ##\displaystyle 4 \left[- 2\cos \frac{t}{2} \right]_0^{\pi} = -8 [0 - 1] = 8##.

Here is my solution to question 6:

Suppose that ##a## is a k-digit integer. So ##a =a_{k-1}a_{k-2} \dots a_2 a_1 a_0 = a_{k-1}10^{k-1} + a_{k-2}10^{k-2} + \cdots a_2 10^2 + a_1 10 + a_0##. Therefore ##b = a_{0}a_{1} \dots a_{k-3} a_{k-2} a_{k-1} = a_{0}10^{k-1} + a_{1}10^{k-2} + \cdots a_{k-3} 10^2 + a_{k-2} 10 + a_{k-1}##. We'll start by computing ##a## mod 9. First, we'll focus on each summand of ##a##. Let ##n \in [0, k-1]##. Then ##\displaystyle a_n 10^n \equiv a_n (1+9)^n \equiv a_n \sum_{i=0}^{n} \dbinom{n}{i} (1)^{n-i}(9)^i \equiv a_n (1 + n 9 + \cdots + n 9^{n-1} + 9^n) \equiv a_n \bmod{9}##. Hence ##a \equiv a_{k-1}10^{k-1} + a_{k-2}10^{k-2} + \cdots a_2 10^2 + a_1 10 + a_0 \equiv a_{k-1} + a_{k-2} + \cdots a_2 + a_1 + a_0 \bmod{9}##. Therefore, ##b \equiv a_{0}10^{k-1} + a_{1}10^{k-2} + \cdots a_{k-3} 10^2 + a_{k-2} 10 + a_{k-1} \equiv a_0 + a_1 + \cdots a_{k-3} + a_{k-2} + a_{k-1} \equiv a_{k-1} + a_{k-2} + \cdots a_2 + a_1 + a_0 \equiv a \bmod{9}##

• QuantumQuest
I have a solution for question 9, but its derivation is very lengthy, with several multiple partial solutions. I was unable to think of a way of avoiding that multiplicity -- it reached 9 at one point.

Mentor
I have a solution for question 9, but its derivation is very lengthy, with several multiple partial solutions. I was unable to think of a way of avoiding that multiplicity -- it reached 9 at one point.
There is a golden way to solve it, but it is certainly not easy to see from the start. But once you have the solution, couldn't you reconstruct from there, which way avoids the large number of cases?

I will try 9:
The solution's rows will be from first to last in line, and the solution's columns will be name, age, top, color, size

Using rules C, G, J, and L gives
Name, Age, Top, Color, Size
--, --, --, --, --
--, 26, --, Yellow, --
--, --, --, --, M
--, --, --, --, --
--, 30, --, --, --

For H, there are two possibilities:
Name, Age, Top, Color, Size
--, 35, --, --, XS
--, 26, --, Yellow, --
--, --, --, --, M
--, --, --, --, --
--, 30, --, --, --

Name, Age, Top, Color, Size
--, --, --, --, --
--, 26, --, Yellow, --
--, --, --, --, M
--, 35, --, --, XS
--, 30, --, --, --

Rule E splits them further:
Name, Age, Top, Color, Size
--, 35, --, --, XS
Stan, 26, Sweatshirt, Yellow, --
--, 27, --, --, M
--, 33, --, --, --
--, 30, --, --, --

Name, Age, Top, Color, Size
--, 35, --, --, XS
Stan, 26, Sweatshirt, Yellow, --
--, 33, --, --, M
--, 27, --, --, --
--, 30, --, --, --

Name, Age, Top, Color, Size
--, 35, --, --, XS
--, 26, --, Yellow, --
--, 33, --, --, M
Stan, 27, Sweatshirt, --, --
--, 30, --, --, --

Name, Age, Top, Color, Size
--, 33, --, --, --
Stan, 26, Sweatshirt, Yellow, --
--, 27, --, --, M
--, 35, --, --, XS
--, 30, --, --, --

Name, Age, Top, Color, Size
--, 27, --, --, --
--, 26, --, Yellow, --
--, 33, --, --, M
Stan, 35, Sweatshirt, --, XS
--, 30, --, --, --

Rules A and F give:
Name, Age, Top, Color, Size
--, 35, --, --, XS
Stan, 26, Sweatshirt, Yellow, S
--, 27, --, --, M
Diana, 33, --, --, XL
Ike, 30, --, Black, L

Name, Age, Top, Color, Size
--, 35, --, --, XS
Stan, 26, Sweatshirt, Yellow, S
--, 33, --, --, M
Diana, 27, --, --, XL
Ike, 30, --, Black, L

Name, Age, Top, Color, Size
--, 35, --, --, XS
Diana, 26, --, Yellow, XL
--, 33, --, --, M
Stan, 27, Sweatshirt, --, S
Ike, 30, --, --, L

Name, Age, Top, Color, Size
Diana, 33, --, --, XL
Stan, 26, Sweatshirt, Yellow, S
--, 27, --, --, M
--, 35, --, --, XS
Ike, 30, --, --, L

Name, Age, Top, Color, Size
Diana, 27, --, --, XL
Ike, 26, --, Yellow, L
--, 33, --, --, M
Stan, 35, Sweatshirt, --, XS
--, 30, --, --, S

Name, Age, Top, Color, Size
Diana, 27, --, --, XL
--, 26, --, Yellow, S
--, 33, --, --, M
Stan, 35, Sweatshirt, --, XS
Ike, 30, --, --, L

Name, Age, Top, Color, Size
Ike, 27, --, --, L
Diana, 26, --, Yellow, XL
--, 33, --, --, M
Stan, 35, Sweatshirt, --, XS
--, 30, --, --, S

Name, Age, Top, Color, Size
--, 27, --, --, S
Diana, 26, --, Yellow, XL
--, 33, --, --, M
Stan, 35, Sweatshirt, --, XS
Ike, 30, --, --, L

Rules B, I, and K trim them down:
Name, Age, Top, Color, Size
Diana, 33, --, --, XL
Stan, 26, Sweatshirt, Yellow, S
Jessica, 27, Shirt, --, M
Valery, 35, Polo Shirt, --, XS
Ike, 30, --, Red, L

Rules D and M:
Name, Age, Top, Color, Size
Diana, 33, T-Shirt, --, XL
Stan, 26, Sweatshirt, Yellow, S
Jessica, 27, Shirt, --, M
Valery, 35, Polo Shirt, Green, XS
Ike, 30, --, Red, L

Rule A:
Name, Age, Top, Color, Size
Diana, 33, T-Shirt, --, XL
Stan, 26, Sweatshirt, Yellow, S
Jessica, 27, Shirt, Black, M
Valery, 35, Polo Shirt, Green, XS
Ike, 30, --, Red, L

The remaining shirt type and color complete the solution:
Name, Age, Top, Color, Size
Diana, 33, T-Shirt, Blue, XL
Stan, 26, Sweatshirt, Yellow, S
Jessica, 27, Shirt, Black, M
Valery, 35, Polo Shirt, Green, XS
Ike, 30, Pullover, Red, L

Mentor
I will try 9:
The remaining shirt type and color complete the solution:
Name, Age, Top, Color, Size
Diana, 33, T-Shirt, Blue, XL
Stan, 26, Sweatshirt, Yellow, S
Jessica, 27, Shirt, Black, M
Valery, 35, Polo Shirt, Green, XS
Ike, 30, Pullover, Red, L
Forgive me that I didn't check the way (mine is of course slightly different), but the result is correct!

Mentor
Here is my solution to question 5:

Every singularity occurs at ##t = 2 \pi n## where ##n \in \mathbb{Z}##. We will compute the arc length from ##0## to ##2 \pi##. From multivariable calculus, we know that when a curve is defined parametrically the arc length along the curve as ##t## varies from ##a## to ##b## is ##\displaystyle \int_a^b \sqrt{\left( \frac{dx}{dt}\right)^2 + \left( \frac{dy}{dt} \right)^2} ~ dt##. Substituting the information we have on hand results in the following integral: ##\displaystyle \int_0^{2 \pi} \sqrt{(1-\cos t)^2 + ( \sin t)^2} ~ dt = \int_0^{2 \pi} \sqrt{2 - 2 \cos t} ~ dt = \sqrt{2} \int_0^{2 \pi} \sqrt{1 - \cos t} ~ dt##. By symmetry of the integrand, we have the equivalent integral ##\displaystyle 2 \sqrt{2} \int_0^{\pi} \sqrt{1 - \cos t} ~ dt##. Note that ##\displaystyle 2 \sin^2 (\frac{t}{2}) = 1 - \cos t##, so we merely have to evaluate ##\displaystyle 4 \int_0^{\pi} \sin \frac{t}{2} ~ dt##, which is equal to ##\displaystyle 4 \left[- 2\cos \frac{t}{2} \right]_0^{\pi} = -8 [0 - 1] = 8##.
Yes, that's correct. The symmetry argument could be replaced by changing ##t \mapsto \frac{1}{2}t## earlier, but this doesn't make a difference. Well done!

QuantumQuest
Gold Member
Here is my solution to question 1:
Well done @Mr Davis 97.

QuantumQuest
Gold Member
Here is my solution to question 6:
Your solution is correct up to the point you express ##b## in the last line. Could you write ##b## in a more clear way and how you reach the expression that is to be proved?

Last edited:
Solution for question 10:
I start with noting that if a matrix ##A## is invertible, then its inverse ##A^{-1}## satisfies ##A A^{-1} = A^{-1} A = I##.

The matrix ##X## has an inverse: ##X^{k-1}##. It is easy to verify that: ##X^{k-1} X = X X^{k-1} = X^k = I##

The matrix ##Y## is nilpotent: ##Y^p = 0## for some positive integer p.

From ##X## and ##Y## commuting, it can be shown that any power of ##X## will also commute with any power ##Y##. I will show that for the inverse of ##X## with ##Y## itself. Take ##X Y = Y X## and multiply both sides by ##X^{-1}##. Then, ## X^{-1} X Y X^{-1} = X^{-1} Y X X^{-1}## or ##Y X^{-1} = X^{-1} Y##.

We wish to find ##Z = X + Y##. Simplify it by setting ##Y = X U##, where ##U = X^{-1} Y##. This gives us ##Z = X (I + U)##. Take a power of ##U##: ##U^m = X^{-m} Y^m##. This means that ##U^p = 0##, and that ##U## is also nilpotent. It can also be shown that all powers of ##U## commute with all powers of ##X##.

It is easiest to do Part (b) first. Set up ##W = 1 - U + U^2 - U^3 + U^4 - ... +(-U)^{p-1}##. Multiply it by ##I+U##:
$$W(1+U) = (1+U)W = 1 + U - U - U^2 + ... + (-1)^{p-1} U^p = I$$
$$Z^{-1} = X^{-1} W$$
By construction,
$$Z^{-1} Z = X^{-1} W X (I + U) = W (I + U) = I ,\\ Z Z^{-1} = X (I + U) X^{-1} W = (I + U) W = I$$
Turning to Part (a), the successful construction of an inverse for Z means that Z is nonsingular.

• StoneTemplePython
StoneTemplePython
Gold Member
2019 Award
This works, and is a variant of the standard answer.
- - - -
A tiny bit of cleanup (i.e. consistent use of ##\mathbf I## not ##1##) would help readability, e.g. here:

It is easiest to do Part (b) first. Set up ##W = 1 - U + U^2 - U^3 + U^4 - ... +(-U)^{p-1}##. Multiply it by ##I+U##:
$$W(1+U) = (1+U)W = 1 + U - U - U^2 + ... + (-1)^{p-1} U^p = I$$

- - - -
directly showing the inverse of ##\mathbf Z##, well, shows it is invertible.

However, it may be worth noting that ##p(1) \neq 0## for the characteristic polynomial of a nilpotent matrix, but this is exactly what is given by ##\det\big(-\mathbf X^{-1}\mathbf Y - \mathbf I \big) ## hence we know

##\det\big( \mathbf Z\big) = \det\big(\mathbf X + \mathbf Y\big) = \det\big(\mathbf Y + \mathbf X\big) = \det\big(-\mathbf X\big) \det\big(-\mathbf X^{-1}\mathbf Y - \mathbf I \big) \neq 0##

I have got the solution to question 3 as follows
angles are A=60, B=105 , C=15 (all in degrees)
BD/CD = tan(15) ...(15 also is in degrees)
I am having a hard time uploading the proof as I've done it in a note book and I am not quite sure how to write mathematical statements here.(I am well aware of the rules)
I have the scanned images of the notebook answers, can someone tell how to upload here?

Mentor
I have got the solution to question 3 as follows
angles are A=60, B=105 , C=15 (all in degrees)
BD/CD = tan(15) ...(15 also is in degrees)
I am having a hard time uploading the proof as I've done it in a note book and I am not quite sure how to write mathematical statements here.(I am well aware of the rules)
I have the scanned images of the notebook answers, can someone tell how to upload here?
Uploads are only second best solution, if not third as they cannot be accessed (on the bottom right of this edit window is the functionality for it, or use the image icon next to the smiley). Under Info you will find this https://www.physicsforums.com/help/latexhelp/ which includes the basis to write LaTeX. It's really not very difficult and in case you want to post more frequently on PF or you will have to write science articles elsewhere, it's worth learning it. Here are two other helpful pages:
http://detexify.kirelabs.org/symbols.html
https://www.sharelatex.com/learn/Spacing_in_math_mode

For the ratio, the precise value was asked for, i.e. a real number (root expressions are allowed), not the tangent of an angle.

Last edited:
Solution for question six :
We have ##a = a_0a_1...a_n## and ##b = a_na_{n-1}...a_0## (would work for any order though), we could rewrite them as ##a = (a_n * 10^0) + (a_{n-1} * 10^1) + ... + (a_0 * 10^n)## and ##b = (a_0 * 10^0) + (a_1 * 10^1) + ... + (a_n * 10^n)## and we know that ##10^n \equiv 1 ## thus ##a \equiv b ##

Last edited:
QuantumQuest
Gold Member
Solution for question six :
What you write is correct but it is not a full solution.

What you write is correct but it is not a full solution.
Alright let me edit a little.

Solution for question six :
We have ##a = a_0a_1...a_n## and ##b = a_na_{n-1}...a_0## (would work for any order though), we could rewrite them as :
##a = (a_n * 10^0) + (a_{n-1} * 10^1) + ... + (a_0 * 10^n)## and ##b = (a_0 * 10^0) + (a_1 * 10^1) + ... + (a_n * 10^n)## and we know that ##10^n \equiv 1 ## which gives us ##a \equiv a_n + a_{n-1} + ... + a_0 ## and also ##b \equiv a_0 + a_1 + ... + a_n ##
Moreover, addition is commutative ##=> a \equiv b ##

What you write is correct but it is not a full solution.
Here is my solution to question 6:

Suppose that ##a## is a k-digit integer. So ##a =a_{k-1}a_{k-2} \dots a_2 a_1 a_0 = a_{k-1}10^{k-1} + a_{k-2}10^{k-2} + \cdots a_2 10^2 + a_1 10 + a_0##. Therefore ##b = a_{0}a_{1} \dots a_{k-3} a_{k-2} a_{k-1} = a_{0}10^{k-1} + a_{1}10^{k-2} + \cdots a_{k-3} 10^2 + a_{k-2} 10 + a_{k-1}##. We'll start by computing ##a## mod 9. First, we'll focus on each summand of ##a##. Let ##n \in [0, k-1]##. Then ##\displaystyle a_n 10^n \equiv a_n (1+9)^n \equiv a_n \sum_{i=0}^{n} \dbinom{n}{i} (1)^{n-i}(9)^i \equiv a_n (1 + n 9 + \cdots + n 9^{n-1} + 9^n) \equiv a_n \bmod{9}##. Hence ##a \equiv a_{k-1}10^{k-1} + a_{k-2}10^{k-2} + \cdots a_2 10^2 + a_1 10 + a_0 \equiv a_{k-1} + a_{k-2} + \cdots a_2 + a_1 + a_0 \bmod{9}##. Therefore, ##b \equiv a_{0}10^{k-1} + a_{1}10^{k-2} + \cdots a_{k-3} 10^2 + a_{k-2} 10 + a_{k-1} \equiv a_0 + a_1 + \cdots a_{k-3} + a_{k-2} + a_{k-1} \equiv a_{k-1} + a_{k-2} + \cdots a_2 + a_1 + a_0 \equiv a \bmod{9}##

For question 2: Yes.

Let's divide the track in 360 equal parts (360 degrees)
Summing all diesel canisters, the car is able to complete at least one full cycle, which means each canister contains an amount of fuel that is enough for the car to run a mininum distance of L = 360/n (n being the number of diesel canisters). For instance: if n = 2, then each canister is enough for the car to run through half the track (L = 360/2 = 180) and so on.

Therefore, for the car not be able to complete the track, each canister must be positioned at a distance X > L from each other. Summing all these distances, we have nX, which is also the total lenght of the track. Therefore:

X > L
nX > nL
nX > n*(360/n)
nX > 360

Which is impossible, since the track has 360 degrees only.

(English is not my main language, and I apologize for any mistakes. I read that question several times, but I still may have committed an intepretation mistake; so sorry in advance!)

Edit: forgot to add one explanation.

StoneTemplePython
Gold Member
2019 Award
Let's divide the track in 360 equal parts (360 degrees)
Summing all diesel canisters, the car is able to complete at least one full cycle, which means each canister contains an amount of fuel that is enough for the car to run a mininum distance of L = 360/n (n being the number of diesel canisters). For instance: if n = 2, then each canister is enough for the car to run through half the track (L = 360/2 = 180) and so on.
I like the gist of this but I didn't follow:

Therefore, for the car not be able to complete the track, each canister must be positioned at a distance X > L from each other. Summing all these distances, we have nX, which is also the total lenght of the track.
It is not that each cannister must be ##\gt L## it is merely that problems can occur if there is even one of those cases-- for any selected sample path, if you hit one of those 'extra long' gaps and don't have enough gas in the tank at the time you encounter it, then you fail.

- - - -
Note: there are some additional challenges in using a discretization argument like this -- what if a car is at the beginning, middle or end of an interval? One could run out of gas in the beginning of an interval with the car at the end of that same interval... If you divide the track into ##K## partitions and select large ##K \gt \gt 360## you can of course get better and better approximations and eventually an arbitrarily good approximation. (For purposes of this problem we may envision the cars as dots /points on this track). I don't think this needs belaboring for Basic challenge, but I will say that strictly speaking this approach does introduce additional technical challenges -- I know of a couple of much simpler solutions that don't require any notion of limits.

You may find it instructive to focus on the 2 cars case a bit more.

QuantumQuest
Gold Member
Alright let me edit a little.

Solution for question six :
After you express ##a## and ##b## as a sum of products there is a more rigorous way in order to show that ##a \equiv b\mod9##. Obviously, I can't tell what it is but as a hint it utilizes polynomials and a known property of modulus.

For @Mr Davis 97 solution see my post #13. Again the same hint I gave you above holds true.

mfb
Mentor
@Thugles: The canisters don't have to have the same amount of fuel and the same distance between them.
They also don't have to be at integer degrees.

Once the problem is solved, it can be interesting to consider what changes if we allow an infinite number of fuel depots. It won't help finding a solution to the finite case, however.