Waste less time on Facebook — follow Brilliant.
×

A nice problem I made

(Assume that there is no friction and drag, and the ball follows the law of reflection.) Suppose we have an \(n\)-gon. There is a point-like ball at the midpoint of one of the sides of the \(n\)-gon (call that side Side A). It is launched to the midpoint of another side (call that Side B). Let \(k\) be the number of sides clockwise to Side A but counterclockwise to Side B (not including Side A and Side B). Define the function \(\delta_n(k)\) to be \(k\) if the ball bounces off every side of the \(n\)-gon before returning to the launch point, and otherwise \(0\). Find the closed form for the sum \[\sum^{n-2}_{k=0}{\delta_n(k)}\]

EDIT: Here is a hint: Euler's Totient Function

And if that doesn't make sense, here is a stepping stone: GCD. (Thanks Calvin L.)

Note by Daniel Liu
3 years, 8 months ago

No vote yet
4 votes

Comments

Sort by:

Top Newest

A better hint would be Greatest Common Divisor, though it might give away too much. Calvin Lin Staff · 3 years, 7 months ago

Log in to reply

I assume you are talking about a regular n-gon? Tim Vermeulen · 3 years, 7 months ago

Log in to reply

@Tim Vermeulen yes. Daniel Liu · 3 years, 7 months ago

Log in to reply

Are you bobthesmartypants? :P Michael Tang · 3 years, 7 months ago

Log in to reply

@Michael Tang Yeah that's what I thought. Ryan Soedjak · 3 years, 7 months ago

Log in to reply

@Michael Tang yep :P Daniel Liu · 3 years, 7 months ago

Log in to reply

Consider a square. \(\delta_{4}(2) = 2\), because the ball will hit all sides before returning to its initial position. Also, \(\delta_{4}(0) = 0\), but that doesn't contribute to the sum. So \[\sum\limits_{k=0}^{2} \delta_{4}(k) = 2\] In general, \[\sum\limits_{k=0}^{n-2} \delta_{n}(k) \geq n - 2\] Another observation I made is that \[\sum\limits_{k=0}^{p-2} \delta_{p}(k) = \sum\limits_{k=0}^{p-2} k = \frac{(p-2)(p-1)}{2}\] for every prime number p. This is because the ball will never return to the initial position before hitting each side in such a p-gon, no matter which side you point the ball at. Tim Vermeulen · 3 years, 7 months ago

Log in to reply

@Tim Vermeulen Sorry, but you answer is incorrect. Solving for the square does not solve it for every other n-gon.

HINT: Euler's totient function Daniel Liu · 3 years, 7 months ago

Log in to reply

@Daniel Liu Yes, I already figured out I should use the Totient function. :) Also, I did not give an incorrect answer, because I did not yet give an answer… I just showed my observations. :)

I know that \[\sum\limits_{k=0}^{n-2} \delta_{n}(k) = - \phi(n) + \sum_{k=1}^{n-1} \begin{cases} k &\mbox{if } \gcd(n,k) = 1 \\ 0 &\mbox{otherwise} \end{cases}\] but that's all I got so far. ;-) Can it get better than this? Tim Vermeulen · 3 years, 7 months ago

Log in to reply

@Tim Vermeulen yep, there is actually a closed form for the second sum on the RHS. Hint on finding the closed sum: What is Gauss famous for as a schoolchild? Daniel Liu · 3 years, 7 months ago

Log in to reply

@Daniel Liu The second term: \[\sum_{k=1}^{n-1} \begin{cases} k &\mbox{if } \gcd(n,k) = 1 \\ 0 &\mbox{otherwise} \end{cases}\] is the sum of all values \(k\) smaller than \(n\) that are coprime to \(n\). These values \(k\) seem symmetric about \(\frac{n}{2}\). For example, if \(n=6\) then \(k=1\) or \(k=5\). And (intuitively) this works for any \(n\). So basically, the average for all values \(k\) is \(\frac{n}{2}\). So the second term in my previous solution is equal to the average \(\left(\frac{n}{2}\right)\) multiplied by the number of terms \(\left(\phi(n)\right)\): \[ \begin{align*} \sum\limits^{n-2}_{k=0} \delta_{n}(k) &= \phi(n) * \frac{n}{2} - \phi(n) \\ &= \phi(n) \left(\frac{n}{2} - 1\right) \end{align*} \] I'm guessing this is the answer? :) That was a very entertaining problem, thanks. Tim Vermeulen · 3 years, 7 months ago

Log in to reply

@Tim Vermeulen that might be a bad hint, so think about this: pairing values up Daniel Liu · 3 years, 7 months ago

Log in to reply

Is the answer zero?? Shubham Srivastava · 3 years, 7 months ago

Log in to reply

@Shubham Srivastava no, sorry. Daniel Liu · 3 years, 7 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...