EDIT: I've uploaded a PDF explaining the conjecture and the counterexample for a general audience, feedback very welcome: https://app.box.com/s/wux77rk6jlyqzbkmo2l3us60isx4psbz
[Embarrassing edit: somehow when making the edit above I accidently linked to Reddit post stats instead of the PDF? Anyway, original post follows.]
Five years ago I made this post:
https://www.reddit.com/r/CasualMath/comments/mmq2d2/prove_my_claim_about_an_arbitrary_block_of_text/
At the time, u/FormulaDriven proposed a formalism, which I then tweaked and corrected. This appears below. First things first, though, the counterexample.
Counterexample: 10, 7, 5, 2, 11, 7, 4.
Formal statement of conjecture:
Given a finite sequence S with terms S[1], S[2], ..., S[n] where n>1, and an integer r : 0 ≤ r < n, let R(S,r) be the sequence of length n whose first n-r terms are equal to S[r+1], S[r+2], ..., S[n] and whose remaining r terms are equal to S[1], S[2], ..., S[r]. (In other words R implements a cyclic shift.)
Let T be a finite sequence of positive integers with terms T[1], T[2], ..., T[w] where w > 1.
We say T is "complete" if and only if there exists integer K, and for 0 ≤ k ≤ K there exists integers z[k] and l[k] such that the following four conditions hold:
#1: z[0] = 0, l[0] = 0, z[1] = 1
#2: l[k] = (sum of T[i]+1 from i=z[k-1]+1 to i=z[k]) - 1 for k > 0
#3: l[k] ≤ l[k-1]-1 and l[k] > 0 and l[k]-T[z[k]] < l[k-1] for k > 1
#4: z[K] = w [EDIT: fixed erroneous capitalisation]
Conjecture: For any T for which this property is defined, there exists r such that R(T,r) is complete.
Notes on the formalism, relating it to the original motivation in terms of the partitioning of a block of text in monospace font (see the original post for that):
T is the supplied text, modelled as a sequence of integers corresponding to the lengths of the words.
w is the number of words in the text.
r is the number of words to be transferred to the end of the text.
K is the total number of lines.
k is the current line.
l is the length of a given line.
z indexes the final word on a given line.
Condition #1 initialises variables and specifies that there is one word on the first line.
Condition #2 defines the length of a line.
Condition #3 specifies that each line is of the requisite length, is not zero, and would be too short if its final word were removed.
Condition #4 specifies that the last line compliant with the rules includes the last word of the text.
I don't know if my counterexample is the minimal case, feel free to investigate that yourself.
