Basic Math Challenge - July 2018

  • #1
fresh_42
Mentor
Insights Author
2021 Award
17,276
17,340
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*}
    \overline{BD}\cdot \overline{CD}&= \overline{AD}\,^2 \\
    \sphericalangle ADB &= 45°
    \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:
  • Like
Likes ISamson, Mr Davis 97, Amrator and 3 others

Answers and Replies

  • #2
prakhargupta3301
58
1
Answering to question 2:
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.

Hence, the answer is no.
(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.
 
  • #3
StoneTemplePython
Science Advisor
Gold Member
1,260
597
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?
 
  • #4
Mr Davis 97
1,462
44
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:
  • Like
Likes QuantumQuest
  • #5
Mr Davis 97
1,462
44
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##.
 
  • #6
Mr Davis 97
1,462
44
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}##
 
  • Like
Likes QuantumQuest
  • #7
lpetrich
987
176
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.
 
  • #8
fresh_42
Mentor
Insights Author
2021 Award
17,276
17,340
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?
 
  • #9
lpetrich
987
176
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
 
  • #10
fresh_42
Mentor
Insights Author
2021 Award
17,276
17,340
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!
 
  • #11
fresh_42
Mentor
Insights Author
2021 Award
17,276
17,340
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!
 
  • #13
QuantumQuest
Science Advisor
Insights Author
Gold Member
926
483
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:
  • #14
lpetrich
987
176
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 $$
The answer:
$$ 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.
 
  • Like
Likes StoneTemplePython
  • #15
StoneTemplePython
Science Advisor
Gold Member
1,260
597
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##
 
  • #16
Pro7
4
1
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?
 
  • #17
fresh_42
Mentor
Insights Author
2021 Award
17,276
17,340
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:
  • #18
archaic
688
210
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 [9]## thus ##a \equiv b [9]##
 
Last edited:
  • #20
archaic
688
210
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 [9]## which gives us ##a \equiv a_n + a_{n-1} + ... + a_0 [9]## and also ##b \equiv a_0 + a_1 + ... + a_n [9]##
Moreover, addition is commutative ##=> a \equiv b [9]##
 
  • #21
archaic
688
210
What you write is correct but it is not a full solution.
Mr Davis had already solved it I think,
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}##
 
  • #22
Thugles
5
0
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.
 
  • #23
StoneTemplePython
Science Advisor
Gold Member
1,260
597
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.
 
  • #24
QuantumQuest
Science Advisor
Insights Author
Gold Member
926
483
Alright let me edit a little.

Solution for question six :

Mr Davis had already solved it I think,

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.
 
  • #25
36,106
13,053
@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.
 
  • #26
Thugles
5
0
I like the gist of this but I didn't follow:
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.

I see the mistake now!

The clarification from @mfb is something I really didn't considerate. I'm having trouble my initial logic, so I'll try a different approach:

Considering U = units of distance and F = units of fuel. Since the total amount of fuel is always enough for the car to complete one cycle, we can assume that the amount of units travelled is the same amount of units of fuel used, which means that, for the complete circuit, ##X = U## (from starting point A to final point A): ##U_{a,a} = F_{a,a}##

(I'm not sure if it's necessary to add but that basically means that we can find a relation of U = kF, where k is a real constant. We are assuming k = 1 for simplification purposes)

Since the car starts without gas, it necessarily has to pick the starting point at one of the canisters.

Assuming N = 2, we have two canisters A and B. Assuming A to be the starting point. The car will fail only if the amount of units travelled (from A to B) is greater than the amount of fuel he has available on that interval, which means ##U_{a,b} > F_{a,b}##. Having in mind that ##U_{a,a} = U_{a,b} + U_{b,a}## and ##F_{a,a} = F_{a,b} + F_{b,a}##, and we know that the whole circle must wield ##U_{a,a} = F_{a,a}##: if the route AB makes the car run out of fuel before reaching canister B, then route BA makes the car arrive in canister A with more than enough fuel: ##U_{b,a} < F_{b,a}## to compensate. Therefore the car could simply start from point B.

This always applies, no matter how many canisters we have. We know it's possible to divide all the fuel available and also divide all the lenght of the track in the same number of partitions. No matter how many canisters we have, there is always a possible starting point. If there is a portion of the track between two canisters (1 and 2) that would make the car run out of fuel before reaching the second canister, it will be compensated by another portion of the track where the car will reach the second canister with more fuel than necessary (that "extra" amount is exactly how much the car lacked in the first situation).

(I had some trouble taking these out of my head; I apologize if it got too confusing)
 
  • #27
StoneTemplePython
Science Advisor
Gold Member
1,260
597
Since the car starts without gas, it necessarily has to pick the starting point at one of the canisters.

Assuming N = 2, we have two canisters A and B. Assuming A to be the starting point. The car will fail only if the amount of units travelled (from A to B) is greater than the amount of fuel he has available on that interval, which means ##U_{a,b} > F_{a,b}##. But we know that the whole circle must wield ##U_{a,a} = F_{a,a}##: if the route AB makes the car run out of fuel before reaching canister B, then route BA makes the car arrive in canister A with more than enough fuel: ##U_{b,a} < F_{b,a}## to compensate. Therefore the car could simply start from point B.

I like this quite a bit.

This always applies, no matter how many canisters we have. We know it's possible to divide all the fuel available and also divide all the lenght of the track in the same number of partitions. No matter how many canisters we have, there is always a possible starting point. If there is a portion of the track between two canisters (1 and 2) that would make the car run out of fuel before reaching the second canister, it will be compensated by another portion of the track where the car will reach the second canister with more fuel than necessary (that "extra" amount is exactly how much the car lacked in the first situation).

I'm not quite buying this argument. Yes, if things are not uniform, (at least) one canister must have an "extra amount". But how do we know that you can always get this "extra amount" without first running out of gas, merely by choosing a 'good' starting position?

(I had some trouble taking these out of my head; I apologize if it got too confusing)

I think your intuition is good here. The fact that you have the ##N=2## case locked down and you're having trouble translating thoughts to paper for the general case would strongly hint at trying to formalize the ##N > 2## case, perhaps in terms of a smaller subproblem that you've already solved...
 
  • #28
QuantumQuest
Science Advisor
Insights Author
Gold Member
926
483
Regarding problem ##6##: Although a more rigorous argument, using polynomials and the property of modulus that if ##a \equiv b\mod m## then it also holds that ##f(a) \equiv f(b)(\mod m)## where ##f(x)## is a polynomial with integer coefficients, can be used in order to conclude to what is asked in the question, I think that @Mr Davis 97 can get the solution credit as it becomes evident from his solution that finally ##a \equiv b\mod 9##. Also, @archaic's solution is along the same lines and can be regarded as correct but it came after Mr Davis 97's solution.
 
  • #29
Thugles
5
0
I think your intuition is good here. The fact that you have the ##N=2## case locked down and you're having trouble translating thoughts to paper for the general case would strongly hint at trying to formalize the ##N > 2## case, perhaps in terms of a smaller subproblem that you've already solved...

(Consider a "portion" as being a section of track between two canisters)

We already know it's possible to divide both the total amount of fuel (F) and the total lenght (U) in the same number of partitions. Therefore, ##U = F##.

If we number all the canisters (from 1 to n) in their respective positions, we have, for the general case:

##U = U_{1,2} + U_{2,3} + U_{3,4} + ... + U_{n-1,n}##
##F = F_{1,2} + F_{2,3} + F_{3,4} + ... + F_{n-1,n}##

(I thought about writing the second one as ##F = F_{1} + F_{2} + F_{3} + ... + F_{n}##; instead, intepret ##F_{a,b}## simply as the amount of fuel in canister a)

Since ##U = F##, we have ##U_{1,2} + U_{2,3} + U_{3,4} + ... + U_{n-1,n} = F_{1,2} + F_{2,3} + F_{3,4} + ... + F_{n-1,n} = C## (with C being a real constant)

Therefore, no matter how many "low fuel canisters" or "really lenghty portions" we have; they will be balanced by canisters with more fuel and shorter lenghts. If that didn't happen, the relation wouldn't remain constant.

(But I'm afraid I'm just saying that that the amount of fuel is almost enough, instead of answering the question...?)

I'm not quite buying this argument. Yes, if things are not uniform, (at least) one canister must have an "extra amount". But how do we know that you can always get this "extra amount" without first running out of gas, merely by choosing a 'good' starting position?

I think I can see the "informal" solution but i'm sure sure if I can express that in a mathematical way :frown:
To me, since U = F, distributing the fuel is the same thing as distributing the circle. It's impossible to distribute circle in a way that it's impossible to make the cycle; taking away from one portion means compensating it somewhere else, and we are always going to have a starting point.

The "perfect" way of having the car run the cycle is by distributing the cannisters symmetrically with the same amount of fuel in each of them (therefore the car arrives at each canister exactly when he's about to run out of fuel), which means any canister is a valid starting point. If I want the car to fail, I need to either remove a bit of fuel in one canister and add in on the another one or move one of the canisters a little bit towards either direction, in order to create one particular portion of track that is bigger than the car can reach.

But, due to the symmetry of the arrangement and the circle, removing fuel or adding lenght to a portion would end up adding fuel or removing lenght to another portion. There will always be at least one spot where the amount of fuel required to reach the next canister is greater than the amount of units I need to run, giving me "extra" fuel to compensate the places where I was supposed to dail.

(Thanks for all the clarifying replies. Now I realize I underestimated that question quite a bit! Last try for today, I promise)
 
  • #30
36,106
13,053
(But I'm afraid I'm just saying that that the amount of fuel is almost enough, instead of answering the question...?)
So far you only demonstrated that your overall fuel balance will work out - but that was given already.

In general, there will be only one starting point where you can complete the circle. Given the positions and fuel amounts, how can you find this point?
 
  • #31
StoneTemplePython
Science Advisor
Gold Member
1,260
597
I'm not sure what happened to the spoiler tags, but I'll nest your responses in them, for space reasons:

(Consider a "portion" as being a section of track between two canisters)

We already know it's possible to divide both the total amount of fuel (F) and the total lenght (U) in the same number of partitions. Therefore, ##U = F##.

If we number all the canisters (from 1 to n) in their respective positions, we have, for the general case:

##U = U_{1,2} + U_{2,3} + U_{3,4} + ... + U_{n-1,n}##
##F = F_{1,2} + F_{2,3} + F_{3,4} + ... + F_{n-1,n}##

(I thought about writing the second one as ##F = F_{1} + F_{2} + F_{3} + ... + F_{n}##; instead, intepret ##F_{a,b}## simply as the amount of fuel in canister a)

Since ##U = F##, we have ##U_{1,2} + U_{2,3} + U_{3,4} + ... + U_{n-1,n} = F_{1,2} + F_{2,3} + F_{3,4} + ... + F_{n-1,n} = C## (with C being a real constant)

Therefore, no matter how many "low fuel canisters" or "really lenghty portions" we have; they will be balanced by canisters with more fuel and shorter lenghts. If that didn't happen, the relation wouldn't remain constant.

(But I'm afraid I'm just saying that that the amount of fuel is almost enough, instead of answering the question...?)


So if you were allowed to choose the sequencing then the above equations would work. However the problem is that I mischievously get to choose the sequencing of the gas canisters. You don't get to permute them / choose their ordering in general. You can only choose where you start in the cycle (i.e. a cyclic property).


I think I can see the "informal" solution but i'm sure sure if I can express that in a mathematical way :frown:
To me, since U = F, distributing the fuel is the same thing as distributing the circle. It's impossible to distribute circle in a way that it's impossible to make the cycle; taking away from one portion means compensating it somewhere else, and we are always going to have a starting point.

The "perfect" way of having the car run the cycle is by distributing the cannisters symmetrically with the same amount of fuel in each of them (therefore the car arrives at each canister exactly when he's about to run out of fuel), which means any canister is a valid starting point. If I want the car to fail, I need to either remove a bit of fuel in one canister and add in on the another one or move one of the canisters a little bit towards either direction, in order to create one particular portion of track that is bigger than the car can reach.

But, due to the symmetry of the arrangement and the circle, removing fuel or adding lenght to a portion would end up adding fuel or removing lenght to another portion. There will always be at least one spot where the amount of fuel required to reach the next canister is greater than the amount of units I need to run, giving me "extra" fuel to compensate the places where I was supposed to dail.

(Thanks for all the clarifying replies. Now I realize I underestimated that question quite a bit! Last try for today, I promise)

Since this is a Basic thread, the argument needs to be fairly tight though perhaps not completely airtight. What I'm strongly hinting at is:

you solved it explicitly for the ##N = 2## case and have identified some interesting structural features for general ##N##. Why not try to solve it explicitly for ##N=3## and perhaps explicitly for ##N=4##. What kinds of patterns can you find here? There's no shame in solving multiple base cases. Then with a pinch of insight you can put it all together in a seamless inductive proof. (I trust you're somewhat familiar with induction in math, or recursion in programming... this is a very nice exercise for it. If you're not, or don't want to go this way, mfb is hinting at another approach)

(Thanks for all the clarifying replies. Now I realize I underestimated that question quite a bit! Last try for today, I promise)
It's ok to submit another one -- as long as you seem to be making incremental progress / putting in a real effort it's fine by me.


In general, there will be only one starting point where you can complete the circle. Given the positions and fuel amounts, how can you find this point?

@Thugles --this seems to hint at the other solution I'm aware of -- a very slick thought experiment that shows how to quickly find the 'right' starting position which gives you existence for free.
- - - -
There certainly may be even more approaches though these are the 2 mains ones I'm aware of.

As a reminder: if different people solve the same problem in significantly different ways, then they both get credit. It's worth exploring different approaches for interesting problems.

edit:
There's also a real nice way to set this one up for a contradiction. So that's 3 distinct solution approaches that I'm aware of...
 
Last edited:
  • #32
BWV
1,210
1,321
Ok here is a stab at #7, apologies if my writing is hard to follow - trying to describe what I did in a spreadsheet

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) what is the expected number of balls chosen before obtaining the first yellow ball?
b) what is the expected number of different colors of balls obtained before getting the first yellow ball?


The probability of drawing a yellow ball is ¼ and the distribution of the number of trials before the first yellow ball is drawn follows a geometric distribution

a) The expectation of a geometric distribution is 1/p. p=1/4 so the expectation is 4 balls (the distribution is skewed so the median is significantly less: 2.4 balls)

b) The probability of a the first success at draw n follows a geometric distribution with p= ¼.

At each draw before the first success there are ( combinations of picking k balls with ##\binom n k## with k<=n

There is a ¼ probability that k=0 (a success in the first trial)

Let s=turn when first yellow ball is drawn and 0<n<s a prior (non-yellow) draw for s>1

Let M = a k x n matrix (each column is a draw and each row is ##\binom n k##,
, the number of combinations of balls of different colors drawn, with 0 if k<n)

Then S = normalizing M, dividing each column vector entry by the sum of that column vector, so that the sum of each column vector =1

Let v= a nx1 (column) vector with each entry representing the probability mass function corresponding to the geometric distribution with p=1/4 and k=n+1 (k=trial of first yellow ball is drawn)

Then multiply Mv , which gives the probability for 1,2,3 different colors of balls for n (every outcome except a yellow ball on the first draw) Mv ≈ (0.502,0.269,0.224)

Let P = (0.25 0.75(Mv)) (0.25,0.377,0.202,0.168), the probabilities corresponding to 0,1,2,3 different colored balls drawn

The expectation is the dot product of (0,1,2,3) and P, which 1.26 expected different colored balls drawn before the first yellow one
 
  • #33
StoneTemplePython
Science Advisor
Gold Member
1,260
597
Ok here is a stab at #7, apologies if my writing is hard to follow - trying to describe what I did in a spreadsheet

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) what is the expected number of balls chosen before obtaining the first yellow ball?
b) what is the expected number of different colors of balls obtained before getting the first yellow ball?


The probability of drawing a yellow ball is ¼ and the distribution of the number of trials before the first yellow ball is drawn follows a geometric distribution

a) The expectation of a geometric distribution is 1/p. p=1/4 so the expectation is 4 balls (the distribution is skewed so the median is significantly less: 2.4 balls)

b) The probability of a the first success at draw n follows a geometric distribution with p= ¼.

At each draw before the first success there are ( combinations of picking k balls with ##\binom n k## with k<=n

There is a ¼ probability that k=0 (a success in the first trial)

Let s=turn when first yellow ball is drawn and 0<n<s a prior (non-yellow) draw for s>1

Let M = a k x n matrix (each column is a draw and each row is ##\binom n k##,
, the number of combinations of balls of different colors drawn, with 0 if k<n)

Then S = normalizing M, dividing each column vector entry by the sum of that column vector, so that the sum of each column vector =1

Let v= a nx1 (column) vector with each entry representing the probability mass function corresponding to the geometric distribution with p=1/4 and k=n+1 (k=trial of first yellow ball is drawn)

Then multiply Mv , which gives the probability for 1,2,3 different colors of balls for n (every outcome except a yellow ball on the first draw) Mv ≈ (0.502,0.269,0.224)

Let P = (0.25 0.75(Mv)) (0.25,0.377,0.202,0.168), the probabilities corresponding to 0,1,2,3 different colored balls drawn

The expectation is the dot product of (0,1,2,3) and P, which 1.26 expected different colored balls drawn before the first yellow one

Sorry. A correct answer only uses symbols like "r, g, b, y" (and perhaps 1, since these are probabilities and sum to one). Note the problem does not say there are only 4 balls in the urn or that odds of drawing a ball are uniform. It says every ball has one color and there are 4 distinct colors in total and the probability of drawing a given ball color is given by ##r## for red, ##g## for green, ##b## for blue and ##y## for yellow.
 
  • #34
Question about 8: What is ##A##? Is it an arbitrary set?
 

Suggested for: Basic Math Challenge - July 2018

  • Last Post
3
Replies
93
Views
4K
  • Last Post
4
Replies
137
Views
13K
  • Last Post
3
Replies
88
Views
6K
  • Last Post
2
Replies
42
Views
4K
  • Last Post
2
Replies
61
Views
5K
  • Last Post
3
Replies
100
Views
4K
  • Last Post
Replies
16
Views
4K
  • Last Post
3
Replies
101
Views
13K
  • Last Post
4
Replies
114
Views
4K
  • Last Post
3
Replies
102
Views
5K
Top