Hall's theorem may get involved. I tried a geometric approach marking a set of x's and a set of y's on a regular polygon and trying to match. Marking the sets is the first problem, however.

The number problem was created to represent a problem on trinomial multiples of a primitive polynomial. They belong to a Hamming code, and hence keep a Hamming distance >=3. I have a "window" on the set of exponents (1,2,3,...) consisting of three separate blocks of 4 successive exponents and want to know how many of the trinomials (with constant term) can fit into it when factored with some X^i. I think that more than 5 trinomials cause two of them to be at distance 2. This problem corresponds with n=7, m=11 after some translation, and its solution seems to be 5. Broader windows give larger n,m. The number problem doesn't seem technical and it looks easy (as I first thought).

There is a computer algebra solution. Form the generating function

1+q+..+q^m=f(q)

and ask Maple to expand f(q)^2.  Count the number of different powers of q you get.

It is a nice idea to let Maple  do the "dirty part". The number of occurring exponents of x gives the number of different results i+j with i, j

Dear Marcel,

maybe there is a direct link with partitions of integers. You are looking for partitions of integers in exactly two parts and distinct. Let B(n) be this function. Then you need to sum B(n) for n ranging from 1 up to m. I would be surprized if B(n) has not been studied in the literature.

Actually, I found this

http://www.mathpages.com/home/kmath556/kmath556.htm

Let me reply on the previous posts one by one. I am pleasantly surprised by the use of Prolog: it is indeed the kind of program that could do a systematic trial-and-error (what I call "dirty combinatorics"). That the specific example (n=7, m=11) has a solution of size 7 is another surprise: my trial-and-error always got stuck after 5 triples. The extension suggested for odd n and m=(3n+1)/2 is correct.

There is a link with partial  n*n latin squares: the set of all triples in 1..n that sum to m+1 can be seen this way with (i=column, j=row, k=color). My problem asks for the largest size of a (partial) transversal. Peter has shown that for n odd and m = (3n+1)/2 there is a full transversal. For n even or m>(3n+1)/2, the claim is that no (full) transversal exists.

p2(1+2j) = p2(2+2j) = j so the sum of p2(x) for x=2...11 is 0+1+1+2+2+3+3+4+4+5. That is too large for the case n=7, m=11.

Finding the number of partitions of x

Peter, The "pairs" version is a slightly more general (weaker) problem than the "3 rows" version, which is the closest translation of the original problem in cryptanalysis.

The viewpoint of partial latin squares may be of help to make sense of your data. Your previous example comes from a "legitimate" partial 7*7 latin square to which you add one row and one column in front and you invent a new color with the odd name of 12 at the new  corner. To make this extension be of the correct type (triples with i+j+k=14), you have to add three empty rows and three empty columns and introduce three non-used colors 9,10,11. This does not feel like the end of a story.

My original concern was to have as few as possible "dangerous" trinomials within an opportunity window. This amount corresponds with the quantity

       largest length of a transversal.

Although this interpretation only concerns n=7, m=11, I use  it as a guiding principle to see where the challenge lies. In your example, you could set Prolog at work to see if you can have still longer transversals in case n=12 and m+1=14. Obviously, your transversal cannot be extended in the 12*12 square.

I assume you were testing the case n=8, m=13. Did you try n=8, m=12 yet?

PS . I occasionally used Prolog some twenty years ago. It would take me some time to get the feeling back. Unfortunately I don't have Prolog on my laptop and I haven't found out yet if I cany have it at the university were I enjoy hospitality nowadays .

You are free to experiment with deviating conditions in your programs (it may pay off), but the cleanest problem design is to have complete symmetry in X,Y,Z. If some Z needs to be 12, then n should be at least 12 and each number in 1..12 is welcome as a value of X, Y or Z.

You seem to go for full sequences at the price of using an excessive value. But it is (at least) equally interesting to keep to the ranges and prove a shortage of length if that's the case. In fact, that is what I hoped to get with n=7 and m=11....

I haven't seen all the details of your program yet, but I would expect a lot of backtracking to handle such a proof. Prolog should be good at this.

I am currently writing a program in C that finds maximal sequences. I hope to get some additional documentation this way to make sure statements.

I emphasize that the "pairs problem" is a weaker version of the "triples problem" with its equivalent formulation of partial transversals.

As for now, I have to drive my wife to the hospital for two days, which will be my main occupation for so long.

I believe that the following pattern works for odd numbers n = 2k+1 and m at least 3k+2.  I suspect that if m is less than 3k+2, an adjustment of this pattern is the best one can do.

(2k+1, k+1), (2k-1, k+2), ..., (1, 2k+1), (2k, 1), (2k-2, 2), ..., (2, k)

That is, we start with the highest number for x and decrease by twos until we get to 1, while the y values increase by ones.  The first sum is the maximum m = 3k+2.  After the first run we start with the highest even value of x paired with 1 for y.  Again the x-values decrease by two and the y-values increase by one.

Thomas, that is a complete solution for the odd case n=2k+1, m=3k+2. Nice.

 Along the lines of what Thomas wrote, here is an idea for n=2k and m=3k. Take the ordered pairs (2k-(2i-2),k+i-1) from i=1 to i=k. Then take the ordered pairs (2k-(2i-1),i) from i=1 to k-1. This should give 2k-1 different pairs that meet all of your conditions. The sums would range from 3k to k+2. 

So it seems that the answer to your initial question, about how many pairs of number between 1 and n meet all those conditions is:

A) n, if n is odd of the form 2k+1 (realized by Thomas's pattern)

B) n-1, if n is even of the form 2k (realized by this one)

Both are provided that m is large enough of course, either 3k for even or 3k+2 for odd.

Something seems wrong with the latter design (e.g. first row does not contain 1, and the send row does not contain k so that these are not permutations).

Probably, a similar construction for n=2k should be as follows:

First take the ordered pairs

(2k-2i+2, k+i) for i=1,...,k;

next take the ordered pairs

(2k-2i+1, i) for i=1,...,k.

This should give the needed n=2k diffrent pairs with the sums taking all values within the range from 3k+1 to k+1 except of 2k+1

 Good easy fix. So start from k+1 instead of k for 2nd coordinate and it is enough to get n=2k different pairs, using otherwise the same formula. Thanks I.E. Kaporin. Seems completely settled now.

A) n=2k. Use (2k-(2i-2),k+i) for i=1 to i=k, then use (2k-(2i-1),i) for i=1 to k. 

B) n=2k+1. Use (2k-(2i-3),k+i) for i=1 to k+1, then use (2k-(2i-2),i) for i=1 to k.

That's a complete solution of the pairs problem.

The narrower triples problem deals with triples (x,y,z) having a fixed sum  and values in the range 1 .. n appearing at most once at each coordinate position. Every solution is a (partial) transversal  in the partial latin n-square where position (x,y) is colored with z iff (x,y,z) has the required sum.

Extending the above solutions of the pairs problem to triples with the smallest possible sum, we find the following.

n=2k+1, sum=3k+2 has n triples as desired. This is even a full transversal.

n=2k, sum=3k+2 produces n triples as desired except for one detail: the last triple produced is (2k-2k+1,k,z) where z=(3k+2)-(1+k)=2k+1. This is outside the range 1..n.

So the question remains whether the even-sized partial latin n-square has a transversal of length n.