∀n ∈ N, ∃w1, w2, . . . , wn ∈ A+ such that w = w1w2 . . . wn and C(w) = C(wi) ∀i ∈ {1, . . . , n}

Question

A is a finite set of letters and A+ denotes the set of all finite length strings formed by letters in A, i.e. ∀w ∈ A+, w is a string, each letter in w belongs to A and len(w) ≥ 1. E.g.- If A = {a, b} then aba ∈ A+ and len(aba) = 3 Now every finite length string u ∈ A+ is assigned a cost between 1 to 100, given by the cost function C : A+ → {1, 2, . . . , 100}. Show that for any natural number n, there is a finite length string w in A+ which can be factored into a concatenation of n strings or factors such that the overall cost of the word is same as the cost of each of those factors. In other words, show that ∀n ∈ N, ∃w1, w2, . . . , wn ∈ A+ such that w = w1w2 . . . wn and C(w) = C(wi) ∀i ∈ {1, . . . , n} (Note that the example is just for clarification and the problem is over any general finite set of letters)

Answer 1

This is a weird question, because we can find the required words already in set $\{a\}^+$ for any letter $a\in A$ (what should be expected because the question concerns also one-letter alphabet $A$). Next, for one-letter alphabet the claim is a corollary of more strong theorems. For instance, Rado Theorem [Pro, 9.3] for an equation $x_1+\dots+x_{100}-y=0$ or Hindman Theorem for natural numbers [Pro, 6.4].

References

I. Protasov. Combinatorics of numbers, VNTL Publishers, 1997.