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
    Jan 10, 2019 at 18:54
  • $\begingroup$ @GerhardPaseman I do not see an easy reduction. Please post your answer. $\endgroup$
    – Mohammad Al-Turkistany
    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
    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
    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
    Jan 10, 2019 at 21:12

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.