13
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ If we construct a graph with the integers from 1 to n as vertices and an edge between any two numbers that sum to a square, this question is asking for the highest n such that the resulting graph is tripartite. Testing whether a graph is tripartite is NP-complete; there is no simple check for it. $\endgroup$ – user2357112 supports Monica Jul 18 '16 at 16:38
  • $\begingroup$ @user2357112 If this is the case, then wouldn't the two vertices that share an edge still be in the same set? You want the opposite - i.e. no such edge exists between elements of any set. $\endgroup$ – Trenin Jul 18 '16 at 16:54
  • $\begingroup$ @Trenin: You might have misread the definition of a k-partite graph. All edges have to go from one part to a different part; edges between members of the same part are forbidden. $\endgroup$ – user2357112 supports Monica Jul 18 '16 at 16:57
  • 1
    $\begingroup$ Is there a nice way to get to the answer instead of a brute force approach like that used by @czarlarry though? $\endgroup$ – Jonathan Allan Jul 18 '16 at 21:41
  • $\begingroup$ This would be a nice problem on math.SE, wanna ask it there too? $\endgroup$ – Ovi Jul 19 '16 at 20:01
6
$\begingroup$

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
>>>

$\endgroup$
  • $\begingroup$ Welcome to Puzzling.SE. I've formatted your code, please check whether the same gives any error message or not (i'm currently using mobile so won't be of much help). $\endgroup$ – ABcDexter Jul 18 '16 at 20:36
  • $\begingroup$ Just added return ret to genGraph $\endgroup$ – Jonathan Allan Jul 18 '16 at 20:40
  • 1
    $\begingroup$ Made it compatible with Python3 while still working in Python2. Also Added a function to return the example stacks that the graph represents (while making sure all stacks contain at least one card) and provided usage. $\endgroup$ – Jonathan Allan Jul 18 '16 at 21:34
  • 1
    $\begingroup$ I don't know if this is linked but 84+85=169=13*13 so we reach a new perfect square at this moment $\endgroup$ – Fabich Jul 19 '16 at 10:33
  • 1
    $\begingroup$ I also tried to figure out why the graph stops being tripartite at 86. Basically, what's added to the graph at this stage is the node 86 with its 4 edges (connecting it to 14, 35, 58 and 83). 86 cannot get any of the three colours, as the four neighbours have to have three different colours. (This can be seen from the '85' graph.) In particular, either (14, 35 and 58) or (14, 58 and 83) have to have three different colours. I couldn't find a simple explanation as to why this is. (I'm not sure there is one - dropping a small number of random nodes from the '85' graph changes this behaviour.) $\endgroup$ – Angkor Jul 21 '16 at 11:09
4
$\begingroup$

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^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.

$\endgroup$
  • 1
    $\begingroup$ Your attempted simplification doesn't work. If we build a graph whose vertices are integers from 1 to n, where an edge exists between any two integers that sum to a square, you're testing for the presence of a 4-clique in the graph, but we really need to test if the graph is tripartite, or 3-colorable. This problem is NP-complete even for planar graphs; the constraints propagate in complex ways that make it harder than just looking for a 4-clique. $\endgroup$ – user2357112 supports Monica Jul 18 '16 at 17:08
  • $\begingroup$ I don't really understand why the problem given is isomorphic to the problem you give. If we do find such a four-clique we've found an n that wont work, right? $\endgroup$ – Jonathan Allan Jul 18 '16 at 18:11
  • 1
    $\begingroup$ Yes, but even without such a 4-clique, it might be impossible to find a valid 3-coloring. For example, take a look at the pentagon with a point in the middle in this image, and imagine if the vertices of the graph were integers and the edges represented two numbers adding up to a square. $\endgroup$ – user2357112 supports Monica Jul 18 '16 at 18:13
  • $\begingroup$ @user2357112 OK so I will find an upper bound then :) $\endgroup$ – Jonathan Allan Jul 18 '16 at 18:16
  • 4
    $\begingroup$ I love these comments. Reading them - for me - feels like puzzle in itself. $\endgroup$ – BmyGuest Jul 18 '16 at 21:47
2
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ This seems to work for n=85 : [[1, 4, 6, 13, 14, 17, 18, 20, 25, 26, 28, 33, 34, 37, 40, 42, 49, 52, 54, 57, 62, 65, 70, 73, 76, 78, 85], [2, 5, 9, 10, 21, 22, 24, 29, 30, 32, 38, 41, 45, 46, 48, 50, 53, 56, 58, 61, 64, 66, 69, 74, 77, 81, 82, 84], [3, 7, 8, 11, 12, 15, 16, 19, 23, 27, 31, 35, 36, 39, 43, 44, 47, 51, 55, 59, 60, 63, 67, 68, 71, 72, 75, 79, 80, 83]] $\endgroup$ – Fabich Jul 18 '16 at 16:15
  • $\begingroup$ @Lord of Dark. Yeah that looks good. Have you managed to get higher than this? $\endgroup$ – hexomino Jul 18 '16 at 16:27
  • $\begingroup$ no I take random samples at each steps but it always stops at 85 or before $\endgroup$ – Fabich Jul 18 '16 at 16:41
  • 1
    $\begingroup$ Well I've done more test and it keeps ending at 85. If only I had enough power or an optimised script to check it... but now I'm pretty sure 85 is the upper bound, or at least something very special happens there ! $\endgroup$ – Fabich Jul 18 '16 at 18:20
1
$\begingroup$

Partial Answer

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}

$\endgroup$
  • $\begingroup$ I'm curious on how you found this. $\endgroup$ – Marius Jul 18 '16 at 14:13
  • $\begingroup$ All this shows is a way to do it for the given n, right? So by "The minimum for n is" you mean "a lower bound minus 1 for n is" assuming it is possible all n lower than that, yes? $\endgroup$ – Jonathan Allan Jul 18 '16 at 14:34
  • $\begingroup$ @Marius You get that if you start at 1 and put each number in the first possible set without making a square sum. $\endgroup$ – f'' Jul 18 '16 at 14:36
  • $\begingroup$ but this does not guarantee there is no other solution for a bigger number. It just proves you can take this approach up to a specific number. $\endgroup$ – Marius Jul 18 '16 at 14:38
  • $\begingroup$ Yes it's just a partial answer that proves that "the maximum value that n can take" is bigger than 34 $\endgroup$ – Fabich Jul 18 '16 at 14:45
1
$\begingroup$

Partial Answer

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 :

Number of possibilities to make 3 stacks

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
 

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This doesn't work. For example, consider a hypothetical where $a+b$, $b+c$, $c+d$, $d+e$, and $e+a$ are all squares, and adding $x$ to any of $a$, $b$, $c$, $d$, or $e$ also produces a square. These numbers have to be split into at least 4 sets, but there is no set of four of them for which every pair sums to a square. $\endgroup$ – user2357112 supports Monica Jul 18 '16 at 17:29
  • $\begingroup$ I am not sure I follow. Why is there an e? I am looking for 4 numbers $\endgroup$ – Marius Jul 18 '16 at 17:44
  • $\begingroup$ You're looking for 4 numbers, but looking for 4 numbers isn't enough. The example I gave is a situation where a 4-number check wouldn't be sufficient. It's based on a standard example of a graph with chromatic number 4 and no 4-cliques. $\endgroup$ – user2357112 supports Monica Jul 18 '16 at 17:46
  • $\begingroup$ It might help to look at the pentagon with a point in the center in this image. $a$, $b$, $c$, $d$, and $e$ are the vertices of the pentagon, and $x$ is the point in the center. $\endgroup$ – user2357112 supports Monica Jul 18 '16 at 17:48
  • 1
    $\begingroup$ It starts to get clear. It might not be enough to find 4 numbers but it is mandatory. $\endgroup$ – Marius Jul 18 '16 at 17:57
-2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Omg im sooo srry, why doesbt spoiler tag work... $\endgroup$ – Shervin Sorouri Jul 19 '16 at 19:18
  • $\begingroup$ Ok seems i fixed it... Srry again... $\endgroup$ – Shervin Sorouri Jul 19 '16 at 19:31
  • 1
    $\begingroup$ If by "S(A)" you mean the sum of the elements in A, then you should re-read the question. It doesn't say that the sum of the subsets is not a perfect square. It says that the sum of any pair of elements from within a set is not a perfect square. $\endgroup$ – Duncan Jul 19 '16 at 20:31
  • $\begingroup$ @Duncan: sorry my bad... $\endgroup$ – Shervin Sorouri Jul 20 '16 at 15:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.