You have n cards that have been numbered from 1 to n. You will divide these cards into three stacks such that, the sum of the numbers of any pair of cards taken from any stack will not be a perfect square. Under this condition what is the maximum value that n can take?
If n=9, three stacks can be divided as (1,2), (3,4,7,8), (5,6,9) and the sum of any pair will not be a perfect square.
I found that the range
n = 3 to 85 inclusive
was possible, but
n = 86 was not
Solution:
Made a graph with each edge connecting vertices whose sum is a perfect square. I then three colored the graph using a backtracking sort of algorithm. Basically an implementation of the situation user2357112 described.
Code (Python):
from __future__ import division
from math import sqrt
def genGraph(l):
ret = []
for k in range(0, l+1):
ret.append([0,[]])
top = int(sqrt(l+l-1))
for k in range(2, top+1):
for k2 in range(1, k*k//2+1):
if(k*k-k2 != k2 and k2 < len(ret) and k*k-k2 < len(ret)):
ret[k2][1].append(k*k-k2)
ret[k*k-k2][1].append(k2)
return ret
def color2(g):
g[1][0] = 1
return color2H(g, 1)
def color2H(g, n):
if(n >= len(g)):
return g
vc = [1,2,3]
for k in g[n][1]:
if(k < n and g[k][0] in vc):
vc.remove(g[k][0])
if(len(vc)==0):
return
for k in vc:
g[n][0] = k
if(color2H(g, n+1)):
return g
g[n][0] = 0
return
def makeExampleStacks(coloredGraph):
stacks = [[] for s in range(3)]
for v in range(1, l + 1):
stacks[coloredGraph[v][0] - 1].append(v)
for i in range(1,3):
if len(stacks[i]) == 0:
stacks[i].append(stacks[0].pop())
return stacks
Use cases:
1. Show a possible distribution for $85$:
>>> for stack in makeExampleStacks(color2(genGraph(85))): ... print(stack) ... [1, 2, 4, 9, 10, 13, 17, 20, 22, 25, 28, 30, 33, 37, 38, 41, 46, 49, 50, 57, 58, 65, 66, 69, 73, 74, 76, 81, 82, 85] [3, 7, 8, 11, 15, 16, 19, 23, 24, 27, 31, 35, 36, 39, 43, 44, 47, 51, 52, 55, 59, 60, 63, 67, 68, 71, 72, 75, 79, 80, 83] [5, 6, 12, 14, 18, 21, 26, 29, 32, 34, 40, 42, 45, 48, 53, 54, 56, 61, 62, 64, 70, 77, 78, 84] >>>
2. Show $86$ is impossible:>>> if color2(genGraph(86)): ... print("possible") ... else: ... print("impossible") ... impossible >>>
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:
and:(((2, 359), (2, 3362), (359, 3362)), 482)
$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$
Edit: This (original route) is not quite right...
For a brute force approach that does not explode as fast as a naive approach we can note that
at the maximal $n+1$ (the first impossible point) there will be $4$ pairs summing to square numbers such that there are only $4$ numbers used across the pairs and $1$ of these will be in all $4$ pairs (thus we cannot split these $4$ pairs into $3$ stacks).
Edit: not right because:
There will never be such a set of four pairs - as one number would have to be in one of the pairs twice.
Furthermore
if we have the square pairs for $n-1$ we can find the square pairs for $n$ by just inspecting the new pairs that may be formed and appending them to the ones for $n-1$.
We may
be able to improve upon this when we are checking for the condition by only inspecting new combinations of $4$ square pairs formed.
but i have not done that yet.
Code so far:
from itertools import combinations
# note: this will return non-square pairs if n gets big, due to the floating point arithmetic
def squarePairs(n, prevKnown=[], prev=0):
res = list(prevKnown)
newCards = [i for i in range(prev + 1, n + 1)]
for a in newCards:
for b in range(1, a):
if ((a + b) ** .5) % 1 == 0:
res.append((b, a))
return res
def findImpossible():
n = 3
sPs = squarePairs(n)
fSPsSet = set()
while 1:
for fSPs in combinations(sPs, 4):
fSPsSet.clear()
for fSP in fSPs:
for i in fSP:
fSPsSet.add(i)
if len(fSPsSet) == 4 and any(sum(1 for fSP in fSPs if i in fSP) == 4 for i in fSPsSet):
return n, fSPs
print("{0} is possible".format(n))
sPs = squarePairs(n + 1, sPs, n)
n += 1
findImpossible is currently running and has shown that
$3$ to $75$ inclusive are possible.
I have computed the number of possibilities for each n (the number of ways we can make the 3 stacks). It confims that n=85 is the maximum, the highest number of possibilities is 7619346 for n=41. I don't know what to do with it but it might help someone to solve it :
n number_of_possibilities 2 3 3 4 4 9 5 18 6 36 7 72 8 144 9 288 10 576 11 1152 12 2304 13 3072 14 4096 15 5120 16 10240 17 20480 18 40960 19 55296 20 74304 21 98384 22 132068 23 182936 24 233720 25 323152 26 445464 27 623276 28 782192 29 954344 30 954344 31 1258056 32 1703706 33 1489096 34 1320119 35 1145964 36 1646108 37 2315230 38 3323978 39 4754466 40 6953224 41 7619346 42 6288985 43 5070996 44 3322568 45 2505684 46 2035007 47 1408492 48 964234 49 1104016 50 1388292 51 1122328 52 951420 53 820878 54 758979 55 812308 56 848847 57 784393 58 713755 59 695534 60 502734 61 305033 62 125214 63 76664 64 70928 65 55729 66 33338 67 22795 68 18242 69 8638 70 5525 71 4902 72 5488 73 3226 74 3144 75 1811 76 849 77 576 78 443 79 483 80 513 81 622 82 742 83 912 84 563 85 187 86 0
Partial Answer: Lower Bound
I have found a solution for
$n=60$
With the following sets
$\{45, 49, 43, 58, 7, 20, 1, 11, 56, 22, 39, 30, 26, 50, 13, 33, 47, 37, 41, 46, 52, 60, 28 \}$, $\{55, 5, 29, 3, 57, 23, 34, 38, 32, 36, 19, 27, 53, 42, 25, 12, 14, 40, 10, 18, 21, 8, 16, 51 \}$, $\{9, 24, 31, 4, 15, 6, 35, 54, 59, 2, 17, 44, 48 \}$
Although, this is also just a lower bound.
P.S. Please feel free to check my sets.
The minimum for n is
34
We could make the following division :
{1-2-4-6-9-11-13-17-18-20-22-26-28-33} {3-5-7-8-10-12-14-16-19-21-23-25-27-32-34} {15-24-29-30-31}
Partial strategy.
Let's say that N is the first number for which this is impossible.
This means we have to find 4 different number up to N for which any combination of 2 add up to a perfect square.
Let's make these numbers $x_1 < x_2 < x_3 < x_4$
Among these numbers, the last one is actually the number N.
This means:
$x_1 + x_2 = k_1^2$
$x_3 + x_4 = k_2^2$
$x_1 + x_3 = k_3^2$
$x_2 + x_4 = k_4^2$
$x_1 + x_4 = k_5^2$
$x_2 + x_3 = k_6^2$
where all $k_i$ are integers.
From the equations above and the imposed order of the numbers we get that:
$k_1^2 \neq k_3^2$
$k_1^2 \neq k_5^2$
$k_3^2 \neq k_5^2$
Also, adding the equations 2 by 2 we get :
$x_1 + x_2 + x_3 + x_4 = k_1^2 + k_2^2 = k_3^2 + k_4^2 = k_5^2 + k_6^2$
From the last 2 things proved above we get that
the sum $x_1 + x_2 + x_3 + x_4$ can be written as a sum of 2 squares in at least 3 different ways.
I got stuck here a bit and called my good friend Google and he gave me this:
http://www.rowan.edu/colleges/csm/departments/math/facultystaff/osler/110%20SUM%20OF%20TWO%20SQUARES%20IN%20MORE%20THAN%20ONE%20WAY%20MACE%20Small%20changes%20Oct%2008%20%20Submission.pdf
In the pdf linked, there is a list of numbers that can be written as 3 different sums of squares.
Example: $325 = 1^2+18^2 = 6^2+17^2 = 10^2+15^2$
in this case 1, 18, 6, 16, 10, 15 are the $k$ numbers we are looking for.
Based on the order of the numbers we imposed, we get that $x_1+x_2$ has the smallest value among the numbers listed above, and $x_3+x_4$ is the largest.
G0ing further we can establish this: $k_1 < k_3 < k_4<k_2$.
And we cannot fit in this chain, $k_5$ and $k_6$.
So in the example above we would have:
$x_1 + x_2 = 1$
$x_3 + x_4 = 18^2$
$x_1 + x_3 = 6^2$
$x_2 + x_4 = 17^2$
$x_1 + x_4 = 10^2 or 15^2$
$x_2 + x_3 = 15^2 or 10^2$
or
$x_1 + x_2 = 1$
$x_3 + x_4 = 18^2$
$x_1 + x_3 = 10^2$
$x_2 + x_4 = 15^2$
$x_1 + x_4 = 6^2 or 17^2$
$x_2 + x_3 = 17^2 or 6^2$
Obviously this won't work because $x_1 + x_2 > 2$ but this was just an explanation.
I also tried for the next number 425 but got nowhere.
And I kind of lost my patience at 5125.
I will pick this up later again, but in case someone wants to continue, feel free to write an answer based on mine and I will gladly upvote it.
Well i personally believe that:
This procedure can be done for all n. Correct me if im wrong please.
Something we will need later:
T1: Two perfect squares differ by atleast 3. Proof: x >=1: (x+1)^2-x^2= 2x+1 >= 3
Ok the base my proof is:
I will use induction on n. The induction base can be n=9 as in the question. In the induction step we know that the hypothesis is true for n=k-1 now we need to prove the hypothesis for n =k.
Ok now the proof begins:
Now we construct our 3 sets for n=k-1. Now we name the sets :A,B,C. Now if the numbers 2 and 1 are in A and we add k to A, and S(A) becomes a square according to T1 if we take 2 or 1 S(A) will be not a squre and if we add for exmaple 2 to another set and it doesnt become a square then its ok otherwise we dont pick 2 and we pick 1. In the case which only one of 1, 2 are in A(say x is that number), if when adding k to A, the sum becomes a square we can take x and put it in the set where the other of 1,2 is if that set becomes a square we can just add the other number back to A. Now if both of 1,2 are in the same set other than A, if when adding k to A its sum becomes a square we can give 1 to A if the other set becomes a square too we can switch 1 and 2. Now the last case: if 1,2 are in separate sets other than A, we can do the above procedures for another set like B because this case ia covered. This solution (all of it) depends on T1.
I hope my answer is atleast partially true.
