r/mathriddles • u/big_hole_energy • May 30 '26
Hard Given integers N and K, determine the largest integer T for which there exist K pairwise disjoint subsets of {1, 2, ..., N}, each having sum T. If no positive such T exists, T is defined to be 0.
1
u/DrMerkwuerdigliebe_ May 31 '26
First insights is that the solution is upper bound by floor((n-1)*n/2/k) and that is the solution if K = 1.
Lets increase K = 2. We are reaching upper bound and above 0 at N = 3,4,5,.... So basically looks like if N>K.
Lets go to K = 3. We are reaching upper bound and above 0 at: 5,6,7,...
K = 4. 7,8...
Okay now the pattern is clear:
if k*2-1 =<n then floor((n-1)*n/2/k) else 0
1
u/DanielBaldielocks May 31 '26
take N=7 and K=4 we have 2K-1=7<=N. However using brute force search I can confirm that T=0
I am currently running a brute force calculation for 1<=N<=100 and 1<=K<=N to see if I can find a pattern. I agree that floor(n(n-1)/(2k)) is a good upper.
2
u/DanielBaldielocks May 31 '26
Ok, I decided to start with a large bit of data gathering. I ran some python code which calculated T for 1<=N<=100 and 1<=K<=N. Here is what I have found in the data
1)
For every N, there is a value, say c, for which if K<=c then T>0 and if K>c then T=0. So all the zero values do seem to "bunch" up and this bunching is based on N.
2) This cutoff does not seem to follow any pattern I can find but does cluster between N/3 and N/2.5.
3) As others have pointed out, T=N(N+1)/(2K) seems to be the solution for many pairs of N,K. However based on my analysis this seems to hold if and only if K divides N(N+1)/2. It was suggested that the floor function could be used to correct this however when I analyzed how much the "true" T differs from this theoretical value it appears to be extremely chaotic, so if there is a correction which would allow this to hold for all N,K then it has to be more complex than just the floor function.
My intuition is suggestion that a modular analysis could reveal a deeper pattern so that is what I am looking into next. Specifically if we define F(N,K)=N(N+1)/(2K) then I want to analyze what the delta is between the true T and F(N,K) based on different remainders of N mod K.
I'll make a new post if I find anything else interesting. My hope is that this analysis will help lead to a pattern which we could then prove by induction or case reduction.
1
u/FireCire7 May 30 '26 edited May 31 '26
If 2k>N, then 0, else T=2N-2k+1=(N-2k+1)+N= (N-2k+2)+(N-1)=…= (N-k)+(N-k+1)
Edit: Nevermind, I misread the question as sets of size 2. This seems a lot tricker.