-6
\$\begingroup\$

Consider a horizontal line with vertical lines centered on the x-axis and placed at gaps of \$\sqrt{2}/2\$. For a positive integer \$n \geq 3\$, the first half of the lines have lengths \$0, \sqrt{2}, 2\sqrt{2}, 3\sqrt{2}, \dots, (n-1)\sqrt{2}\$ and then the second half have lengths \$(n-2)\sqrt{2}, (n-3)\sqrt{2}, \dots, 0\$.

The goal is to find a circle center on the horizontal line so that for every pair of consecutive vertical lines, there exists a circle with that center which fits between them without touching either of them. For example, in the following illustration we can see that if we picked the origin for \$n=3\$ and the center at the origin, it is possible.

enter image description here

For \$n = 4\$, we can see that the center can't be at the origin.

enter image description here

We instead will need to move the center to the left. If we move the center to -1, then it is just possible.

enter image description here

For \$n=5\$ a center at -1 doesn't work and neither does -2.

enter image description here

For \$n=5\$ the desired output is -3.

Task

Given an integer \$n \geq 3\$, output the largest integer valued circle center \$ x \leq 0\$ so that there exists a circle with that center for each pair vertical lines that goes between the vertical lines and doesn't touch them.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Any counterexample where the longest one isn't bottleneck? \$\endgroup\$
    – l4m2
    Jan 15 at 10:41
  • \$\begingroup\$ @l4m2 It's a great question. I don't have a counterexample but that doesn't mean they don't exist. \$\endgroup\$
    – Simd
    Jan 15 at 10:42
  • \$\begingroup\$ Why the downvote? \$\endgroup\$
    – Simd
    Jan 15 at 12:10

1 Answer 1

3
\$\begingroup\$

JavaScript (Node.js), 24 bytes

n=>(n*4-2-n*n)/8**.5-1|0

Try it online!

Any counterexample where the longest one isn't bottleneck?

Looks correct. Proof: scale the circle smaller and see how the allowed distance also get smaller

Used WolframAlpha

\$\endgroup\$
2
  • \$\begingroup\$ You're the best golfer there ever was! \$\endgroup\$
    – enzo
    Jan 15 at 11:00
  • \$\begingroup\$ I hope someone is able to prove this correct. \$\endgroup\$
    – Simd
    Jan 15 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.