Timeline for What sequence maximizes the final distance?
Current License: CC BY-SA 4.0
30 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2023 at 18:40 | history | edited | Arthur Queiroz Moura | CC BY-SA 4.0 |
Remove irrelevant information
|
| S Mar 29, 2023 at 16:02 | history | bounty ended | CommunityBot | ||
| S Mar 29, 2023 at 16:02 | history | notice removed | CommunityBot | ||
| Mar 25, 2023 at 13:39 | comment | added | Arthur Queiroz Moura | By manipulating the "generalized cossine law" I put, it's possible to prove that if the segment on the extremity has a greater length than its adjacent segment, then swapping them will always increase the value of the distance. Maybe this can help us prove that at the endpoints of the segment list we have either a 0 or a 1 | |
| Mar 25, 2023 at 1:27 | comment | added | Arthur Queiroz Moura | For the angles, if we consider the simmetry, permutations do seem unimodal. For $n \geq 4$, we seem to have $2^{n-4}+1$ permutations. Of these, $2^{n-4}$ are unimodal ones with endpoints $n-2$ and $n-3$. The other one has endpoints $n-2$ and $n-4$ | |
| Mar 24, 2023 at 20:01 | history | edited | Arthur Queiroz Moura | CC BY-SA 4.0 |
sort arrangements; edit edit2's example
|
| Mar 24, 2023 at 18:05 | comment | added | Claude Chaunier | Cool, there are $2^{n-3}$ unimodal permutations of $0,1, \dots, n-1$ starting with and ending with 0, as we choose to put $2$ after $0$ onto the left or before $1$ onto the right, then $3$ onto the left or onto the right, $\dots$ | |
| Mar 24, 2023 at 17:43 | comment | added | Arthur Queiroz Moura | I updated the link. Now the arrangements are better. Also, I noticed that there are $2^{n-3}$ possible arrangements of the $l$'s | |
| Mar 24, 2023 at 17:42 | history | edited | Arthur Queiroz Moura | CC BY-SA 4.0 |
edited body
|
| Mar 24, 2023 at 17:33 | comment | added | Claude Chaunier | How about displaying your arrangements with less visual clutter, such as $$\begin{matrix}023451-42103\\ 023541-42103\\ 024531-31024\\ \dots\end{matrix}$$ and sorting them ? | |
| Mar 24, 2023 at 17:23 | comment | added | Claude Chaunier | Up to $n=6$, the valid optimal sequences of segment indices seem to be exactly the unimodal permutations of $0, 1, ...,n-1$ with $0$ on one end and $1$ on the other end. The corresponding optimal sequences of angle indices always seem unimodal too, but with more variety with the end points, and not all unimodal permutations allowed. | |
| Mar 24, 2023 at 17:21 | history | edited | Arthur Queiroz Moura | CC BY-SA 4.0 |
Include solutions counted by a_n at pastebin link
|
| Mar 24, 2023 at 17:01 | comment | added | Claude Chaunier | I find the same lower bounds up to $n=6$ with $10^6 \times (2n-1)$ independant uniform pseudo-random 64 bits-float numbers as well, in Rust. I scaled the angles so that their sum is $\pi/2$ truncated to 7 decimals, and then tried with $\pi/2/100$ as well, and it made no difference with the variety of solutions. | |
| Mar 22, 2023 at 14:14 | history | edited | Arthur Queiroz Moura | CC BY-SA 4.0 |
add example at the end which shows that the naive algorithm doesn't work
|
| S Mar 21, 2023 at 14:21 | history | bounty started | Arthur Queiroz Moura | ||
| S Mar 21, 2023 at 14:21 | history | notice added | Arthur Queiroz Moura | Draw attention | |
| Mar 19, 2023 at 11:35 | comment | added | Arthur Queiroz Moura | Sorry, I messed the order of the angles. You're supposed to rotate by $\alpha_1$ first (i.e. put $l_0$ rotate $\alpha_1$, put $l_2$ rotate $\alpha_0$ and then put $l_1$). With this, you go from (0, 0) to (1, 0). Then to (3.4, 1.8). Then to (4.6, 3.4). So the distance squared is 32.72 > 32.32. | |
| Mar 19, 2023 at 4:50 | comment | added | user44143 | Let’s take lengths 1,2,3 and angles arcsin(7/25), arcsin(4/5)-arcsin(7/25), which use Pythagorean triples to get nice decimal coordinate moves. As I see it, Joseph’s algorithm goes from (0,0) to (3.00,0.00) to (4.92,0.56) to (5.52,1.36), a squared distance of 32.32; the algorithm you suggest goes from (0,0) to (1.00,0.00) to (3.88,0.84) to (5.08,2.44), a squared-distance of 31.76. Is this a counterexample, or what’s wrong in my calculations? | |
| Mar 19, 2023 at 1:44 | comment | added | Arthur Queiroz Moura | @MattF. Actually, this case ($n=3$) has already been completely solved: as stated in my question, no matter what are the values of the fixed and given segment lengths and angles, we have that, out of the $\dfrac{3! 2!}{2}$ possible arrangements, the following is always the one which maximizes the distance. If $l_0 < l_1 < l_2$ are the lengths and $\alpha_0 < \alpha_1$ the angles, the best arrangement is always built by putting $l_0$ first, rotating by $\alpha_0$, then putting $l_2$, rotating by $\alpha_1$ and then putting $l_1$. So for $n=3$ his algorithm always fails | |
| Mar 19, 2023 at 1:07 | comment | added | user44143 | Will you give an example of three lengths and two angles where Joseph’s algorithm fails? | |
| Mar 18, 2023 at 13:34 | comment | added | Arthur Queiroz Moura | It also fails for the solved n=3 case | |
| Mar 18, 2023 at 13:30 | comment | added | Arthur Queiroz Moura | @JosephO'Rourke surprisingly, this already fails for n=4. What I observed was a central tendency in which longer lengths and small angles tend to be in the middle. For n=4, the 3 possible cases I found were 1) ls 0 2 3 1 angs 2 0 1 || 2) ls 0 3 2 1 angs 2 0 1 || 3) ls 0 2 3 1 angs 1 0 2 || (for example (1) means that l_0 (the lowest) is put first, then rotate by alpha_2 (the biggest angle), put l_2, rotate by alpha_0 (the smallest angle), put l_3 (the biggest length), rotate by alpha_1 (the middle angle) and then put l_1 (the second smallest length) ) | |
| Mar 18, 2023 at 13:22 | comment | added | Joseph O'Rourke | Naively, this seems a candidate: sort the lengths, longest to shortest. Sort the angles, smallest to largest. Then match the longest length with the smallest angle. And continue: 2nd longest length with 2nd smallest angle. And so on. | |
| Mar 18, 2023 at 13:17 | history | edited | Joseph O'Rourke | CC BY-SA 4.0 |
Included image.
|
| Mar 18, 2023 at 11:36 | history | edited | Arthur Queiroz Moura | CC BY-SA 4.0 |
edited title
|
| Mar 17, 2023 at 22:32 | history | edited | Arthur Queiroz Moura | CC BY-SA 4.0 |
edited title
|
| Mar 17, 2023 at 22:31 | history | edited | Arthur Queiroz Moura | CC BY-SA 4.0 |
edited title
|
| Mar 17, 2023 at 22:31 | history | edited | Arthur Queiroz Moura |
edited tags
|
|
| S Mar 17, 2023 at 19:12 | review | First questions | |||
| Mar 17, 2023 at 19:33 | |||||
| S Mar 17, 2023 at 19:12 | history | asked | Arthur Queiroz Moura | CC BY-SA 4.0 |