1
$\begingroup$

I developed a puzzle for which I am seeking an EFFICIENT algorithm (I searched Google but did not find this puzzle in the literature, ):

You have $k$ rationals, $n_1/d_1, n_2/d_2, ..., n_k/d_k$.

Query: Is there a way to flip some fractions and get 1 when multiplying all $k$ rationals $\prod_{i=1}^{k} n_i/d_i=1$ (flip turns a rational upside down).

Here is a solvable instance: 243/16, 81/32, 27/162, 8/54, 432/128, 648/36

Is there an efficient algorithm? or Is it NP-complete?

Improve this question
$\endgroup$
13
  • $\begingroup$ How is this different from subset sum or partition? Isn't there an easy reduction? Gerhard "Just Use Many More Fractions" Paseman, 2019.01.10. $\endgroup$
    – Gerhard Paseman
    Commented Jan 10, 2019 at 18:54
  • $\begingroup$ @GerhardPaseman I do not see an easy reduction. Please post your answer. $\endgroup$
    – Mohammad Al-Turkistany
    Commented Jan 10, 2019 at 19:02
  • 2
    $\begingroup$ Take an integer vector (or multiset) with sum of components 2N. Reduce to your problem by sending component t to (2/3)^t. Gerhard "This Is A Simple Reduction" Paseman, 2019.01.10. $\endgroup$
    – Gerhard Paseman
    Commented Jan 10, 2019 at 19:28
  • $\begingroup$ The solution to the given instance is to flip the 1st, 4th, and the 5th fractions. $\endgroup$
    – Mohammad Al-Turkistany
    Commented Jan 10, 2019 at 19:46
  • 1
    $\begingroup$ It may be worth examining the simple version of your puzzle where all n's are powers of two and all d's are 1. The pseudo-polynomial solution of subset sum might become polynomial for you. Gerhard "Prefers Working The Easy Cases" Paseman, 2019.01.10. $\endgroup$
    – Gerhard Paseman
    Commented Jan 10, 2019 at 21:12

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .