Set partition with special constraints

Question

Does anybody has an idea how to find formula for S(n) defined as:

S(n) = min {k ϵ N; for all partitions A₁, A₂, ..., A_n of set A={1,2,...,k} ∃i ∃a, b, c ϵ A_i: a+b=c}

It is obvious that S(1) = 2, S(2) = 5.... But how to define formula for S(n) in general?

Answer 1

This is not an answer, but Brian Scott conjectured in the comments to the question that it was the Catalan numbers. If so, it's probably worthy of inclusion in the list of results on the OEIS page.

Anyway, a simple python script demonstrates the following:

For n=2:
Checking with k = 2
No Ai exists for [[1], [2]]
Checking with k = 3
No Ai exists for [[1], [2, 3]]
Checking with k = 4
No Ai exists for [[1, 4], [2, 3]]
Checking with k = 5
S(2)=5

and

For n=3:
Checking with k = 3
No Ai exists for [[1], [2], [3]]
Checking with k = 4
No Ai exists for [[1], [2, 3], [4]]
Checking with k = 5
No Ai exists for [[1, 4], [2, 3], [5]]
Checking with k = 6
No Ai exists for [[1, 4], [2, 3], [5, 6]]
Checking with k = 7
No Ai exists for [[1, 4], [2, 3], [5, 6, 7]]
Checking with k = 8
No Ai exists for [[1, 4], [2, 3], [5, 6, 7, 8]]
Checking with k = 9
No Ai exists for [[1, 4], [2, 3], [5, 6, 7, 8, 9]]
Checking with k = 10
No Ai exists for [[1, 4, 7], [2, 5, 6], [3, 8, 9, 10]]
Checking with k = 11
No Ai exists for [[1, 5, 8], [2, 6, 7], [3, 4, 9, 10, 11]]
Checking with k = 12
No Ai exists for [[1, 4, 10], [2, 3, 11, 12], [5, 6, 7, 8, 9]]
Checking with k = 13
No Ai exists for [[1, 4, 10, 13], [2, 3, 11, 12], [5, 6, 7, 8, 9]]
Checking with k = 14
S(3)=14

which certainly fits Brian Scott's conjecture.

The next one is computationally challenging. I've established that $k>21$, but it will take a while to get to 42. This is a simple, brute-force kind of code. There are probably cleverer ways to do this...

For n=4:
Checking with k = 4
No Ai exists for [[1], [2], [3], [4]]
Checking with k = 5
No Ai exists for [[1], [2, 3], [4], [5]]
Checking with k = 6
No Ai exists for [[1, 4], [2, 3], [5], [6]]
Checking with k = 7
No Ai exists for [[1, 4], [2, 3], [5, 6], [7]]
Checking with k = 8
No Ai exists for [[1, 4], [2, 3], [5, 6, 7], [8]]
Checking with k = 9
No Ai exists for [[1, 4], [2, 3], [5, 6, 7, 8], [9]]
Checking with k = 10
No Ai exists for [[1, 4], [2, 3], [5, 6, 7, 8, 9], [10]]
Checking with k = 11
No Ai exists for [[1, 4, 7], [2, 5, 6], [3, 8, 9, 10], [11]]
Checking with k = 12
No Ai exists for [[1, 5, 8], [2, 6, 7], [3, 4, 9, 10, 11], [12]]
Checking with k = 13
No Ai exists for [[1, 4, 10], [2, 3, 11, 12], [5, 6, 7, 8, 9], [13]]
Checking with k = 14
No Ai exists for [[1, 4, 10, 13], [2, 3, 11, 12], [5, 6, 7, 8, 9], [14]]
Checking with k = 15
No Ai exists for [[1, 8, 11, 14], [2, 6, 10, 13], [3, 5, 7], [4, 9, 12, 15]]
Checking with k = 16
No Ai exists for [[1, 5, 9, 12, 15], [2, 6, 11, 14], [3, 7, 8], [4, 10, 13, 16]]
Checking with k = 17
No Ai exists for [[1, 6, 9, 13, 16], [2, 7, 12, 15], [3, 8, 10], [4, 5, 11, 14, 17]]
Checking with k = 18
No Ai exists for [[1, 9, 11, 14, 17], [2, 5, 6, 13, 16], [3, 8, 10], [4, 7, 12, 15, 18]]
Checking with k = 19
No Ai exists for [[1, 5, 8, 12, 15, 18], [2, 6, 10, 14, 17], [3, 4, 9, 11], [7, 13, 16, 19]]
Checking with k = 20
No Ai exists for [[1, 9, 11, 13, 16, 19], [2, 6, 7, 10, 15, 18], [3, 4, 5, 12], [8, 14, 17, 20]]
Checking with k = 21
No Ai exists for [[1, 8, 11, 14, 17, 20], [2, 5, 6, 9, 16, 19], [3, 7, 12, 13], [4, 10, 15, 18, 21]]

This is after running overnight...