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

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

Are you bobthesmartypants? :P

Michael Tang - 8 years ago

Yeah that's what I thought.

Ryan Soedjak - 8 years ago

yep :P

Daniel Liu - 8 years ago

I assume you are talking about a regular n-gon?

Tim Vermeulen - 8 years ago

yes.

Daniel Liu - 8 years ago

A better hint would be Greatest Common Divisor, though it might give away too much.

Calvin Lin Staff - 8 years ago

Is the answer zero??

Shubham Srivastava - 8 years ago

no, sorry.

Daniel Liu - 8 years ago

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 - 8 years ago

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 - 8 years ago

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 - 8 years ago

@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 - 8 years ago

@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{aligned} \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{aligned}$ I'm guessing this is the answer? :) That was a very entertaining problem, thanks.

Tim Vermeulen - 8 years ago

@Tim Vermeulen – that might be a bad hint, so think about this: pairing values up

Daniel Liu - 8 years ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$