1
$\begingroup$

I have an array a of n entries. I need to place a token on the first and last position of that array, so a[0] = 1 and a[n-1] = 1.

I now want to place additional tokens into that array with a distance inbetween each index i where a[i] = 1 that is greater than 2 (so placing a token on every index is invalid as well as alternating using and not using an entry is invalid). Phrazed differently: I want that sum(a) < n/2 . The gap inbetween each token should be the same, so say with an array of size 16,

a[0] = 1, a[3] = 1, a[6] = 1, a[9] = 1, a[12] = 1, a[15] = 1

would be a solution with a gap size of 2 (distance of 3).

How do I find all gap sizes that are possible to fill said array with the given constraints?

Imagine a street inbetween two crossroads where a lamppost should be placed on each crossroad and then additional lampposts should be placed equidistant to each other and for some reason only natural number distances are allowed.

(The actual problem I want to solve is where to place Sea Lanterns in my Minecraft Project so do not disregard this problem as an assignment question I want a solution for.)

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

If I understand your problem correctly, the tokens (lanterns) can be placed every $x$ blocks (starting from $0$) if and only if $x>2$ is a divisor of $n-1$.

For example, if the array has $n=31$ elements the valid values of $x$ are $3,5,6,10,15,$ and $30$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ After posting the question and trying out different values for more examples I came to the same conclusion, thanks for validating it. (So the gap sizes are the divisors of n-1 minus 1: 2, 4, 5, 9, 14 in your example, for n=16 they would be 2 and 4, for 144 they would be 11 and 13, sadly for my exact problem of n = 72 , n-1 is a prime so there is no way I can distribute the lanterns equidistant from each other ...) $\endgroup$
    – salbeira
    Commented Jul 4, 2020 at 22:17
  • $\begingroup$ As a workaround for $n=72$ you could leave one extra block "in the middle" to preserve symmetry. Then the possible values of $x$ are $5, 7, 10, 14, 35$, and $70$. You could also place one extra token "in the middle". In this case you also want $x$ to be odd (so that the gap is even and symmetry is again preserved). The possible values are $5$, $7$, and $35$. $\endgroup$
    – Steven
    Commented Jul 4, 2020 at 22:27
  • $\begingroup$ In this case I can also leave $3$ blocks in front and in the back blank so the problem reduces to an array of size $66$ ($72 - 6$) with $n-1$ therefore being $65$ with gaps of size $4$ or $12$. $\endgroup$
    – salbeira
    Commented Jul 4, 2020 at 22:47

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.