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?
