0
$\begingroup$

We wish to either show the following or find a counterexample:

For any two sets of positive integers $A$ and $B$, if $|A| = |B|$, $\sum_{a \in A}^{}a = \sum_{b \in B}^{}b$, and $\prod_{a \in A}^{}a = \prod_{b \in B}^{}b$ then $A = B$

The converse of the statement above is is certainly true, but the truth of the actual conjecture is not obvious.

An equivalent way to express the conjecture is as follows:

Let $S$ and $T$ be finite sequences of positive integers, and let them be the same length. Also, no integer can appear more than once a given sequence. If $\sum_{x \in S}^{}x = \sum_{y \in T}^{}y$ and $\prod_{x \in S}^{}x = \prod_{y \in T}^{}y$ then sequence $S$ is a permutation of sequence $T$

If the conjecture is correct, then the following algorithm will correctly determine whether two one-dimensional arrays of distinct positive integers contain the same elements:

DEFINE FUNCTION permutation_check(ARRAY A, ARRAY B)

    DOUBLE FLOAT acum_log <- 0; // accumulator of logorithmic evaluations
    INT          acum     <- 0; // accumulator 

    FOR i = 1 to A.last_index
        a  <- a  + A[i]  - B[i]

        acum_log <- acum_log + LOG(A[i]) - LOG(B[i])
    END_FOR

    IF (a != 0 or ABSOLUTE_VALUE(acum_log) > 0.0001)
        RETURN "A is NOT a permutation of B"; // certainly correct
    END_IF

    RETURN "A is a permutation of B"; // dubious

END FUNCTION DEFINTION
$\endgroup$
  • 5
    $\begingroup$ Consider the roots of the polynomials $x^3-3x^2+7x-100$ and $x^3-3x^2-20x-100$. $\endgroup$ – Jack D'Aurizio Oct 18 '17 at 17:31
  • $\begingroup$ @JackD'Aurizio wrote, "Consider the roots of the polynomial $x^3−3*x^2+7*x−100 = 0$" However, the set of real root to that polynomial only contains one element, and it is $x ≈ 5.271115886$. That is not an integer. I am only concerned with sets of positive integers. Also, I am mainly interested in sets containing more than one element. $\endgroup$ – Toothpick Anemone Oct 18 '17 at 17:37
  • $\begingroup$ All right, the roots of those polynomials are not positive integers, but they can be made so by a little tweaking. I thought the main idea was clear: just two constraints (on $\sum$ and $\prod$) stand no chance of fixing a whole subset of $\mathbb{N}^+$ with cardinality $\geq 3$. $\endgroup$ – Jack D'Aurizio Oct 18 '17 at 17:49
  • $\begingroup$ On the other hand, this spawns an interesting question about polynomials, i.e. to find two monic third-degree polynomials with positive integer roots, having $mx$ as difference. $\endgroup$ – Jack D'Aurizio Oct 18 '17 at 17:51
  • $\begingroup$ Then 5xum answer can be read as: $x^3-20x^2+81x-90$ and $x^3-20x^2+109x-90$ do the job. $\endgroup$ – Jack D'Aurizio Oct 18 '17 at 17:52
6
$\begingroup$

My initial gut feeling was "I'd bet my left kidney that can't be true". Why? Because you only set two constraints, which might well be enough if you only have two variables (and it turns out, it is), but you have no limitation on the number of variables. Clearly, that can't be true in the reals, and sure $\mathbb N$ is a little more restrictive, but still. I'd bet even just $3$ elements can give a counterexample.


Turns out the gut feeling was right, the answer is No. Take $\{1,9,10\}$ and $\{2,3,15\}$ as a counterexample.

If you are curious, here's the python code I used to find this counterexample (it's a simple brute force search)

def find_counter(n):
    sum_prod = {}
    for a in range(1, n):
        for b in range(a+1, n):
            for c in range(b+1, n):
                s = a + b + c
                p = a * b * c
                if (s,p) in sum_prod:
                    return sum_prod[(s,p)], (a,b,c)
                sum_prod[(s,p)] = (a,b,c)

find_counter(100)
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Π {1, 9,10} = 90 = Π {2, 3,15} . . . . . Σ{2, 3,15} = 20 = Σ {1, 9,10} = 20 Yes! your counterexample works! $\endgroup$ – Toothpick Anemone Oct 18 '17 at 17:44
  • $\begingroup$ this is a minimal counter example, in the sense that n=2 works $\endgroup$ – MCT Oct 18 '17 at 17:48
  • $\begingroup$ @MCT Indeed. Which is why I did a brute force search for $3$-element sets :) $\endgroup$ – 5xum Oct 18 '17 at 17:53
  • $\begingroup$ @5xum I accidentally pressed the return key on my keyboard before I was finished writing my comment. I thought I was inserting a linebreak, not submitting the comment. I had more to say than just $1*9*10 = 90$ $\endgroup$ – Toothpick Anemone Oct 18 '17 at 17:54
  • 1
    $\begingroup$ @ToothpickAnemone I see now. So if my counterexample works, I suggest you accept my answer. (By the way, a little playing around helped me find "even better" counterexamples where more than $2$ sets give the same product and sum. For example, [(15, 88, 140), (16, 77, 150), (20, 55, 168), (24, 44, 175), (25, 42, 176)] is an example of $5$ sets that all give the same sum and product. $\endgroup$ – 5xum Oct 18 '17 at 17:56
1
$\begingroup$

The sets $\{1,2,3\}$ and $\{6\}$ are a counterexample to your first conjecture. The second conjecture is not equivalent to the first, as this counterexample shows.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Sorry, I should have mentioned, the two sets contain the same number of elements. $\endgroup$ – Toothpick Anemone Oct 18 '17 at 17:42
1
$\begingroup$

Just to highlight another method, I simply considered the factorisations of various numbers with lots of factors. I was aiming for a counter-example with three integers.

So with product $36$ I found $2,3,6$ and $3,3,4$, the second of which is not strictly a set, because it has duplicates. But its existence suggested that in larger cases there might be distinct integers. There is also $1,6,6$ and $2,2,9$.

$60$ and $84$ gave nothing, but $72$ had $2,6,6$ and $3,3,8$ and $96$ yielded $1,8,12$ and $2,3,16$.

This was quite quick by hand.

Two further questions suggest themselves: are there examples of three sets of three positive integers having the same sum and the same product? Are there examples of two sets of $n$ positive integers having the same sum and the same product for all $n\ge 3$? Both seem likely based on my hand calculations.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ And one of the other answers indeed finds five sets of three with the same sum and product. $\endgroup$ – Mark Bennet Oct 18 '17 at 18:04
  • 1
    $\begingroup$ "are there examples of three sets of three positive integers having the same sum and the same product?".... here's an example of five :) $\{15, 88, 140\}, \{16, 77, 150\}, \{20, 55, 168\}, \{24, 44, 175\}, \{25, 42, 176\}$. I think the real question is "are there examples of $n$ sets of three positive numbers all with the same sum and product?". $\endgroup$ – 5xum Oct 18 '17 at 18:04
  • $\begingroup$ @5xum Indeed. I am wondering whether there is enough structure to prove that you can find arbitrarily many sets of three, or whether the irregularity of the primes gets in the way too much. I now see that from a set of three I can get a set of four simply by adding a common element to each set. Also a constant multiple of any collection of sets is a solution. If I could multiply all my sets of three by some common factor in such a way that I could construct an another set with the same common sum, I'd be there. $\endgroup$ – Mark Bennet Oct 18 '17 at 18:11
0
$\begingroup$

If $n=1$ it certainly is true. If $n=2$, the claim is true. It says $$a_1 + a_2 = b_1 + b_2 \text{ and } a_1a_2 = b_1b_2 \implies a_1 = b_{1}, a_2 = b_{2}$$ where $a_1< a_2, b_1 < b_2$. This in turn implies $$(a_1 + a_2)^2 = (b_1 + b_2)^2 \implies a_1^2 + a_2^2 = b_1^2 + b_2^2.$$ WLOG suppose that $a_2 \geq b_2$, so let $a_2 = b_2 + k$ for $k \geq 0$. Then $$a_1^2 + 2kb_2 + k^2 = b_1^2$$ $$a_1 = b_1 - k.$$ Plugging in the second into the first gives $$2k^2 = 0$$ hence $k=0$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Sorry, I should have mentioned, the two sets contain the same number of elements. $\endgroup$ – Toothpick Anemone Oct 18 '17 at 17:40

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.