/sci/ - Science & Math

Previous Thread >>10459117

󠛡 󠛡

>>10462198
Plain English would be the last 4 digits of (π) like my password :P

Floens didn't implement a TeX interpreter on Clover, so please post pictures of your solutions for the poor phoneposting bastards like me who's only at home to eat and sleep.

>>10462198
(2n^3 + 3n^2 - 11n + 18)/6

You can generate the sequences easily.
Start with a sequence that attains a maximum.
Ex: 123 yields 11
Insert a 0 between the 1 and 2
1023
Add 1 to each
2134 yields 25.

>>10462198
If n is odd, then sum of squares - (n^2 - 1)/4. When n is even, and larger than 6 The formula is sum of squares - n^2/4. the inner product of a vector of the first n natural numbers with its cycle (of one displacement), so we can maximize this my minimizing the distance between the vectors in R^n (with euclidean distance). Every permutation of the first n natural numbers has the same orthogonal projection onto (1,1,1,....,1), and is the same distance from said orthogonal projection. The group of permutations can be broken into disjoint sets, each generated by applying a cycle of displacement 1 onto a single element (repeatedly). Each set will have exactly n members. Without loss of generality, in each and every set, there is a pair of vectors such that the distance between them is minimal (in comparison to the other pairs in the set containing them). Applying a single displacement cycle onto the minimal vector pair wont change the distance between the resulting vectors, producing another minimal distance pair. This process can be repeated producing exactly n of these pairs. Because there are only n vectors in the set, one can product a graph using the vectors as verticies, and the minimal distance pairs as edges. The graph is a single cycle with n verticies and n edges, where all of the n edges are the same length, and where all n of the verticies are the same distance from the orthogonal projection. This grapth must be a regular, n sided polygon, with radius distance from the projection, to a permutation vector. The n sides, and radius distance determine the side length, so all subsets from the permutation set all have the same minimal distance. So, when you have a permutation of the first n natural numbers, it will have a global distance minimum with its cycle of k displacement. Without loss of generality, we can pick the permutation where the numbers are in ascending order.

>>10463702
When n is odd, k can be (n+1)/2, and we can change the cycle of displacement k into a cycle of displacement 1 by changing the sequence. Instead of a sequence from 1 to n in ascending order, it will be an alternating sequence, with one subsequence counting down from (n+1)/2, and the other subsequence counting down from n. The distance formula from this sequence to its cycle of displacement 1 has all the same terms as the distance formula for the ascending vector to its (n+1)/2 displacement, so this vector pair must have global minimum distance.

putas

>>10463702
A better proof for the graph part would be to say that a cycle of displacement 1 will always move d distance around the circle, and that after repeating this n times, you get the first collision, so d is a ratio of m and n, where m is coprime with n. So, asking the question what x*d + y*1 minimum value is (for integer x and y) is asking what (1/n)*(x*m + y*n)’s minimum value is, which is 1/n. The circumference of the circle is fixed, so 1/n of it will be the global minimum for n.

>>10463959
(Minimum value excluding 0)

>>10463055
Let M(n) denote the maximum possible sum for {1,...,n}
Let {x_i} be any permutation of {1,...,n-1}
S = (x1)*(x2)+(x2)(x3)+...(x{n-1})(x1)
Suppose you want to generate a permutation of length n, by inserting n into the permutation of length n-1 between xk and x{k+1}.
S - (xk)(x{k+1}) + (xk)*n + n*(x{k+1}) = (x1)(x2) + ... + (x{k-1})(xk) + (xk)*n + n*(x{k+1}) + (x{k+1})(x{k+2}) + ...+(x{n-1})(x1)
S - (xk)(x{k+1}) + (xk)*n + n*(x{k+1}) = S'
The biggest increase that is possible going from S to S' is n^2 -2 and it happens when n is inserted between n-1 and n-2 (this requires that the two largest elements are adjacent in S (this property is preserved when S is transformed into S')).
(Just maximize f(x,y)= n(x+y)-xy for x,y in [1,n-1], x != y)

Just do induction from here.
12 attains the maximum of M(2) = 4 and the 2 largest elements are adjacent.
132 attains the maximum of M(3) = 11 and the 2 largest elements are adjacent.
1342 attains the maximum of M(4) = 25 and the 2 largest elements are adjacent.
etc.

M(n) = M(2) + (3^2 - 2) + (4^2 - 2) + ... + (n^2 - 2) = 2+ (2^2 -2) + (3^2 - 2) + (4^2 - 2) + ... + (n^2 - 2)
= 3 + (1^2 - 2) + (2^2 -2) + (3^2 - 2) + (4^2 - 2) + ... + (n^2 - 2)
= 3 -2n + n(n+1)(2n+1)/6

>>10462198
List all evens up to n in ascending order; then list all odds in descending order.

>>10465231
Prove it is maximum

>{x1,x2,…,xn}={1,2,…,n}
Is this a retarded way of referring to the numbers 1 to n?

>>10465721
Can you convey the same meaning with less symbols?

>>10465721
This also annoyed me. The entire problem is written like shit.

>>10465821
Find with proof the largest value of
f(n) = 1 * 2 + 2 * 3 + ... + (n - 1) * n + n * (n + 1)
t. mechE

>>10465918
>t. mechE
Lol