2
$\begingroup$

Problem: Define the set $Q_p := \{a \in \mathbb{Q} \mid 100a \in \mathbb{Z}^+ \}$. Given an integer $k$ and some $n \in Q_p$, find $a = \{a_1, a_2, \cdots a_k\} \subset Q_p$ such that

$$\sum_{i=1}^k a_i = \prod_{i=1}^k a_i = n$$


I'll call $Q_p$ the "price rationals," as they're the fractions whose decimal form can be a price in dollars and cents. (Is there an actual standard form for a subset of this nature, i.e., the rationals that are all of the integers divided by $m$?)

This problem is a generalization of this week's Riddler Express. There, $n = 7.11, k=4$, and the solution is $a = \{3.16,1.5,1.25,1.2\}$. But I came to the answer via a bit of brute force and a bit of factorization ($7.11 = 9\cdot 79 /100 \to 3.16 = 79/25$), and I have to imagine there's a better way.

If $k=2$, then from Vieta's formulas it's clear that $a_1, a_2$ are the roots of $x^2-nx+n = 0$. Not all $n$ will have rational solutions, however; solutions exist only if $n^2-4n = q^2$ for some $q^2 \in Q_p$. So we have a method of determining whether there is a solution, and a method of finding it, for $k=2$. Great! (The same solution, with different existence parameters, would work if we allowed all positive rationals, not just the price rationals.)

But now consider $k=3$. If we try the same method, we get $x^3 -nx^2 + (a_1a_2+a_1a_3+a_2a_3)x -n = 0$. While two of our coefficients are equal to $n$, the third one... isn't. And there's no apparent rearrangement/transformation to get it in terms of $n$.

And it gets worse as $k$ increases, because we're really only given two equations, which is solvable in two variables, but not so much in three, four, etc. We can solve for $a_2, a_3$ in terms of $n$ and $a_1$ for $k=3$, but $a_1$ remains an unbound variable... except that it can't remain unbound, if there's a unique solution. (Which raises the question: can there be multiple solutions? EDIT: Yes! See answer by @paw88789)

Does anyone have thoughts on attacking this systematically for $k=3,4$, or even higher? Or do we end up with factorization followed by trial and error?

$\endgroup$
13

1 Answer 1

1
$\begingroup$

This only answers your question about multiple solutions. There can be multiple solutions to a problem of this type (at least with three values):

$$(0.80)(2.50)(3.30)=.80+2.50+3.30=6.60$$ and $$(1.10)(1.50)(4.00)=1.10+1.50+4.00=6.60$$

[I found these using a computer search with Python.]

$\endgroup$
1
  • 1
    $\begingroup$ Very nice, thank you for the check! At some point brute-forcing with SageMath is a path I'll probably go down, and knowing multiple solutions are possible is greatly useful! I suspect multiple solutions are more likely for abundant numbers (divided by $100$). $\endgroup$ Jun 29, 2022 at 22:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .