Hello, I had this observation while solving a problem, I can tell it is true but I cannot figure out how to concretely prove it. Maybe one of you with better mathematics than me can come up with a proof.
Here is the situation: You are given array of n positive integers. For 1<k<n, can you prove that:
- If k is even, then all subarrays of length k are palindromic IFF the entire array is just a single number repeated
- If k is odd, then all subarrays of length k are palindromic IFF the entire array is either a single number repeated, or two numbers alternating
In the picture I have illustrated the structure for n=9, and k=7 and 8. I draw an arc between two positions if by some palindromic subarray we know these two positions must have equal numbers. You can tell the assertion is true from the pictures.
I tried to prove it myself, and I think there are some tricky issues that you might run into/need to work out:
See Issues - Assume array is 1-indexed. If your proof relies on looking at the subarray starting at index i, and the very next one starting at i+1, and you iterate i thru the array, maybe you prove that for the even case, element at i must equal element at i+1 by looking at these two subarrays. The issue is you can't actually iterate i past n-k+1, so you haven't actually shown that all elements are equal.
- Let's say for the odd case you show that given the equality constraints from your first subarray (i.e., if first subarray palindromic, then we have a1=ak, a2=a_k-1, etc), and equality constraints from your second subarray, then the elements could be all equal or two different numbers alternating. You may have more subarrays than just the first two. Therefore you must verify that the equality constraints from your third subarray for example does not change things, e.g., looking at first two subarrays equality constraints gives that the elements can be same or alternating, but once you add the third, what if this enforces that elements must be equal, thus ruling out the alternating case?
One direction is trivial. For the other direction, we will show by induction.
Let's fix $$$k$$$.
For the base case, we check $$$n=k+1$$$. We have two subarrays of length $$$k$$$, which give us the following properties: for any $$$1 \leq i \lt n$$$, we have that $$$a_i = a_{n-i}$$$ and $$$a_{i+1} = a_{n-i+1}$$$. This gives us that $$$a_1 = a_{n-1} = a_3 = a_{n-3} = a_5 = ...$$$ and $$$a_2 = a_{n-2} = a_4 = a_{n-4} = a_6 = ...$$$. This implies that all elements of the same parity are the same. If $$$k$$$ is even, this implies that all elements are the same because $$$n$$$ is odd, so $$$1$$$ and $$$n-1$$$ are opposite parities.
Now, let's consider $$$n \gt k+1$$$. Since the given property must also hold for all subarrays of length $$$k$$$ of $$$a[1, n-1]$$$, by the induction hypothesis these elements satisfy the desired conclusion. Now, the last element $$$a_n$$$ must be equal to $$$a_{n-k+1}$$$. If $$$k$$$ is odd, these are the same parity, so all elements of the same parity are the same. If $$$k$$$ is even, this implies that all elements are the same.
This suffices to conclude the proof.
Hi thanks a ton, I just finished understanding this, this is very interesting.
[EDIT: I just noticed u fixed the typos, can ignore my comments abt them]
I think you got n and k mixed up here: "If k is even, this implies that all elements of the same parity are the same." I think this is if n is even. (And in the next sentence should be "if n is odd.")
So as I understand it we are saying when n is even, the first set of equalities only involves odd numbers, and second only involves even. However when n is odd, either set of equalities enumerates both the odd and the evens, so they are all equal.
Also near the end the parity is mixed up i think, "If k is even, these are the same parity" should be if k is odd these are the same parity, and vice versa for the next sentence.
I thought about induction but I kept trying to fix n and induct on k lol. The insight here for the base case, where either the parity of the element we are looking at keeps flipping or it stays the same is very nice, and then the induction easily extends that to more subarrays.
Thanks for this, now I can go to sleep lol
Assume, that array is 1-indexed, called this array $$$A$$$.
If $$$k$$$ is even, let's consider indexes $$$i$$$, such that $$$i - \frac{k}{2} + 1 \ge 1$$$ and $$$i + 1 + \frac{k}{2} - 1 \le n$$$. For such $$$i$$$ we have that $$$A[i] = A[i + 1]$$$, because $$$A[(i - \frac{k}{2} + 1):(i + \frac{k}{2})]$$$ is a palindrome by definition. For all $$$k \lt n$$$ we have $$$i = \frac{k}{2}$$$ and $$$i = \frac{k}{2} + 1$$$ satisfy the equality, so we have segment that consists at least of three equal elements ($$$A[\frac{k}{2}]$$$, $$$A[\frac{k}{2} + 1]$$$, $$$A[\frac{k}{2} + 2]$$$, let's they are equal to $$$x$$$). Now let's prove that if $$$A[j] = A[j + 1] = A[j + 2] = y$$$ then $$$A[j - 1] = y$$$. If $$$k = 2$$$, then all $$$i$$$ from $$$1$$$ to $$$n - 1$$$ satisfy the equation in the beggining, so all elements are equal. Let's $$$k \gt 2$$$, then as we have palindrome that in the center has elements $$$j$$$ and $$$j + 1$$$, such palindrome leads to $$$A[j - 1] = A[j + 2] = y$$$, proof is compelete. So all elements to the left from $$$i = \frac{k}{2}$$$ are equal to this $$$x$$$, analogically all elements to the right from $$$i = \frac{k}{2} + 2$$$ are also equal to $$$x$$$, as a result, the entire $$$A$$$ is a single repeated value. Proof is compelete.
If $$$k$$$ is odd notice that $$$A[i]$$$ and $$$A[j]$$$ such that $$$i$$$ and $$$j$$$ have different parity are independent. We can compare elements using only palindrome of odd length, assume that palindrome is 1-indexed, in such palindrome we have $$$A[1 + j] = A[k - j]$$$, then $$$k - j - (1 + j) = k - 1 - 2j$$$ that is an even element, but $$$j - i$$$ with a different parity is an odd element, so they are independent. Proof is complete. For elements with the same parity, using the proof as for even $$$k$$$ (but consider $$$i + 2$$$ instead $$$i + 1$$$) we got that $$$A[1] = A[3] = ... = A[k] = x$$$ and $$$A[2] = A[4] = ... = A[k - 1] = y$$$. If x = y, then $$$A$$$ is a single repeated number, otherwise $$$A$$$ is a two number alternating. Proof is complete.
Sorry, I overkilled the proof and not strictly proof that if we have segment of equal elements then all elements are equal (for that induction required)
I will be glad if my proof helps someone, but for a faster and more strict proof, it is better to use the one above from reirugan