Return to Answer

(((2, 359), (2, 3362), (359, 3362)), 482)

and:
$2+359=19^2$;
$2+3362=58^2$;
$359+3362=61^2$;
$2+482=22^2$;
$359+482=29^2$; and
$3362+482=62$

(((2, 359), (2, 3362), (359, 3362)), 482)

and:
$2+359=19^2$;
$2+3362=58^2$;
$359+3362=61^2$;
$2+482=22^2$;
$359+482=29^2$; and
$3362+482=62^2$

I have a feeling

It may always be possible

The condition to check for may be simplified by noting that

at the maximal $n+1$ (the first impossible point) there will be $6$ pairs summing to square numbers such that there are only $4$ numbers used across the pairs (thus we cannot split these $6$ pairs into $3$ stacks in any way).

An upper bound is

$n = 3361$

Note that

If there are $6$ pairs summing to square numbers such that there are only $4$ numbers used across the pairs then we cannot split these $6$ pairs into $3$ stacks in any way.

Now we can

search for such scenarios by first forming all sets of $3$ pairs that contain $3$ distinct numbers (for example $\{(6, 19), (6, 30), (19, 30)\}$) and then checking for a distinct $4^\text{th}$ number less than the maximum of those that forms a pair with each of the $3$.

Some code:

def squarePairs(n):
    for a in range(1, n + 1):
        for b in range(a + 1, n + 1):
            if ((a + b) ** .5) % 1 == 0:
                yield a, b

def squarePairTriples(n):
    sPs = list(squarePairs(n))
    for ai, a in enumerate(sPs):
        for bi, b in enumerate(sPs[ai + 1:]):
            if a[0] == b[0]:
                c = (a[1], b[1])
            elif a[0] == b[1]:
                c = (a[1], b[0])
            elif a[1] == b[0]:
                c = (a[0], b[1])
            elif a[1] == b[1]:
                c = (a[0], b[0])
            else:
                continue
            if c in sPs[bi + 1:]:
                yield a, b, c

def findD(squarePairTriple):
    tripleVs = set()
    for t in squarePairTriple:
        for v in t:
            tripleVs.add(v)
    for d in range(1, max(tripleVs)):
        if d not in tripleVs:
            for v in tripleVs:
                if ((d + v) ** .5) % 1:
                    break
            else:
                return d

Now we can find an upper bound like so:

>>> g = squarePairTriples(5000)
>>> for t in g:
...     d = findD(t)
...     if d:
...             t, d

The first case that this produces is:

(((2, 359), (2, 3362), (359, 3362)), 482)

and:
$2+359=19^2$;
$2+3362=58^2$;
$359+3362=61^2$;
$2+482=22^2$;
$359+482=29^2$; and
$3362+482=62$

Edit: This is not quite right...

The condition to check for may be simplified by noting that

at the maximal $n+1$ (the first impossible point) there will be $6$ pairs summing to square numbers such that there are only $4$ numbers used across the pairs (thus we cannot split these $6$ pairs into $3$ stacks in any way).

Edit: This (original route) is not quite right...