A Good Time to Refuse The Setup

Suppose you're given n fuses, with 1 &leq; n &leq; 5, each of which is a meter long, and where each fuse has an associated burn rate of N meters per D hours.

A fuse can be lit at one or both ends, subsequently extinguished at one or both ends, relit, re-extinguished, etc., as many times as needed until the fuse is fully consumed. You are able to light and extinguish fuses instantaneously, and you can observe the exact instant a fuse is fully consumed (burnt up).

A fuse cannot be cut nor can it be lit anywhere except at its ends.

Such a setup allows for an infinitely accurate timing system, by measuring the time between any two fuse lighting/consumption events. For example, given two fuses with a burn rate of 1 meter per hour, you can measure exactly 45 minutes (3/4 hours) by


simultaneously: lighting the first fuse at both ends, lighting the second fuse at one end, and marking the start of your time interval
lighting the second end of the second fuse at the instant the first fuse is consumed (30 minutes later)
marking the end of your time interval at the instant the second fuse is consumed (15 minutes later)


The Challenge

Given a fractional number of hours t, and a set of n fractions representing exact burn rates of n fuses, write a program or function that outputs/returns a truthy value if t hours can be precisely measured through systematic burning of the fuses, or a falsy value otherwise.

The input to the program can be any of the following:


command-line arguments of the form TN/TD N1/D1 N2/D2 N3/D3 ...
a string of the form TN/TD N1/D1 N2/D2 N3/D3 ... read from stdin or equivalent
a string of the form TN/TD N1/D1 N2/D2 N3/D3 ... passed as a function argument
an array of strings ["TN/TD", "N1/D1", "N2/D2", "N3/D3", ...] passed as a function argument


In all cases t = TN/TD, where TN,TD &isin; [1,10000].

Likewise, in all cases: burn rate for fuse i = Ni /Di = N&lt;i&gt;/D&lt;i&gt;, where N&lt;i&gt;,D&lt;i&gt; &isin; [1,10] &forall; i.

You may assume there will always be between 1 and 5 fuses (inclusive), and that all inputs are valid and in-range. You may also assume that all input fractions are given in lowest terms.

You may not use floating point numbers with fractional components for this challenge. That is, if you use floating point numbers anywhere in your application, they may only take on integral values with zero fractional component.

Scoring

This is a code-golf challenge, hence the shortest compliant submission in bytes will be awarded the win.



Example Inputs/Outputs

input:  29/6 3/2 2/3 3/5 3/7 7/5
output: true

One solution:
  - light both ends of fuse 1, mark start of interval
  - on fuse 1 consumption: light both ends of fuse 2, light one end of fuse 5
  - on fuse 5 consumption: extinguish one end of fuse 2, light both ends of fuse 3,
    light both ends of fuse 4
  - on fuse 2 consumption: extinguish one end of fuse 3, extinguish both ends of
    fuse 4
  - on fuse 3 consumption: relight one end of fuse 4
  - on consumption of fuse 4: mark end of interval (29/6 hours)

input:  2/1 3/1 5/1 7/1
output: false

input:  5/1 6/1 1/6 9/1 1/9
output: true

One solution:
  - light fuse 1 at one end, light fuse 2 at both ends, light fuse 4 at both ends
  - on fuse 1 consumption: extinguish one end of fuse 2, mark start of interval
  - on fuse 4 consumption: relight one end of fuse 2
  - on fuse 2 consumption: mark end of interval (5 hours)


Happy fusing! :)
Python 2, 305
This is the golfed version. It is practically unusable for n &gt; 3, as the time (and space) complexity is like 3n2... actually that may be way too low for the time. Anyway, the function accepts a list of strings.
def f(i):
 Z=range;r=map(__import__('fractions').Fraction,i);R=r[1:];n=len(R);L=[[[1]*n,[0]]];g=0
 for m,p in L: 
  for d in([v/3**i%3for i in Z(n)]for v in Z(3**n)):
    try:x=min(m[i]/R[i]/d[i]for i in Z(n)if m[i]*d[i]&gt;0);L+=[[[m[i]-x*R[i]*d[i]for i in Z(n)],[p[0]+x]+p]]
    except:g|=p[0]-r[0]in p
 return g

A slightly optimized version can finish the test cases in a couple of minutes. It might still be slow for an impossible n=5 case though.
def fLessslow(i):
 Z=range
 r=map(__import__('fractions').Fraction,i)
 R=r[1:]
 n=len(R)
 L=[((1,)*n,(0,))]
 ls = set(L)
 for m,p in L: 
  if p[0]-r[0]in p: return 1
  for d in([v/3**i%3 for i in Z(n)]for v in Z(3**n)):
   if any(d[i] and m[i]&lt;=0 for i in Z(n)):continue
   try:
    x=min(m[i]/R[i]/d[i]for i in Z(n)if m[i]*d[i]&gt;0)
    thing = (tuple(m[i]-x*R[i]*d[i]for i in Z(n)),(p[0]+x,)+p)
    if thing not in ls:L+=[thing];ls.add(thing)
   except:5
 return 0

print fLessslow('5/1 6/1 1/6 9/1 1/9'.split())
print fLessslow('29/6 3/2 2/3 3/5 3/7 7/5'.split())