4
$\begingroup$

There are $3$ friends $(A,B,C)$ preparing for math exam. There are $N$ problems to solve in $N$ minutes.

It is given that:

  1. Each problem will take $1$ minute to solve. So all $N$ problems will be solved in exactly $N$ minutes.

  2. Only $1$ person will solve a problem, that is if a problem $xyz$ is solved by $A$ , then $B$ and $C$ need not to solve it.

  3. Only one person will solve a problem in any given time. That is if $A$ is solving a problem at any given time, then $B$ and $C$ should remain idle(This will ensure that $N$ problems will be solved in exactly $N$ minutes).

Now there are some constraints:

  1. $A$ being a lover of the number $k$ has decided that the total number of problems solved by him will be a multiple of $k$. (If $k=2$ then $A$ will solve $0$ or $2$ or $4$... problems)

  2. $B$ is a lazy guy. So he will not solve any problem in consecutive minutes. He needs rest after solving $1$ problem.

  3. $C$ will solve atleast $1$ problem.

Determine the number of ways they can solve the problems.

Example: if $N=3$ and $k=0$ , then $A$ will not solve any problem, so there are $4$ ways:($B$ solve $1$st, $C$ solve $2$nd and $3$rd) or ($B$ solve $2$nd, $C$ solve $1$st and $3$rd) or ($B$ solve $3$rd and $C$ solve $1$st and $2$nd) or ($B$ solve $1$st and $3$rd and $C$ solve $2$nd)

Given: $0\le k\le10$

$\endgroup$
  • 1
    $\begingroup$ In your example, what about $B$ solves $1$st and $3$rd and $C$ solves $2$nd? $\endgroup$ – Robert Chamberlain Nov 25 '14 at 11:23
  • $\begingroup$ oh! I forgot that. thanks :) $\endgroup$ – Batman Nov 25 '14 at 11:32
  • $\begingroup$ There are an infinite amount of answers, since there are no bounds on N. Replace N with a specific number, say, 20, and you will probably get an answer from someone. $\endgroup$ – JLee Nov 25 '14 at 12:51
  • $\begingroup$ I need a generalized answer for given N and K $\endgroup$ – Batman Nov 25 '14 at 13:32
0
$\begingroup$

I don't think any formula will be able to capture those rules, for non trivial values of N and k. What is certainly doable is to write an algorithm to determine that number; or even better, the infinite sequence of ways for each natural n, given a fixed k.

Such algorithm will basically "inductively" compute each element of the series based on the previous element. Such element will be internally represented into a split form into a few useful partitions, one for each of the possible state of the current problem solving situation.
Allow me to further explain.

Finite state machine

One instance of your sequence of N problems solutions can be imagined as a sequence of N+1 states of progress into the problem solving. The things you want to remember, during that process, are just $$ a \in [0..k[ = \text{how many problems A solved so far (in modulo k)}\\ b \in [0,1] = \text{1 iff the last problem was solved by B, else 0}\\ c \in [0,1] = \text{1 iff C already solved any problem, else 0} $$ By only knowing these facts (or variables) you are able to determine which are all possible further states, and if one of them is an ending state (i.e. if the current sequence of problem solvers will be one of the ways counted in $w(N)$).

For example, if $a=0, b=0, c=0$ I know that I can go to, depending on the next person who will solve the problem,

  • $A -> a=1, b=0, c=1$ (not an ending state)
  • $B -> a=0, b=1, c=1$ (an ending state)
  • $C -> a=0, b=0, c=0$ (an ending state)

Track all states

Now, notice that all possible states are a finite number, and actually relatively few. The exact amount is $4k$, and in the worst case in which k = 10 (thanks for binding k), you will only have 40 states.
If you know, for each of the $4k$ states, in how many ways you could have got there in exactly n steps, you can determine in how many ways you can get to each of the $4k$ states after step n+1. If you start with 0 problems, with 1 only in $w_0(0,0,0)$ (you can only start from this state in which A solved 0, B didn't solve the last one, and C didn't solve any), and compute the amount of ways $w_i$ for each state, for each i up to n, you will simply have to sum together the ways $w_n(0,0,1) + w_n(0,1,1)$ to get your ways in which n problems were solved and all your rules were honored.

The code

I coded this in Scala, I hope you don't mind the language choice.
Beware that your number grows pretty quickly, and if its value overflows the maximum Java long value ($2^{63}-1$), you will have to replace long variables with a BigInteger or something similar.

import collection.Map // generic Map interface

object ProblemSolverz {
  def main(args: Array[String]): Unit = {
    // C
    println(new ProblemSolverz(3).ways(1))

    // CC, BC, CB
    println(new ProblemSolverz(3).ways(2))

    // CCC, BCC, CBC, CCB, BCB
    println(new ProblemSolverz(3).ways(3))

    // CCCC
    // BCCC, CBCC, CCBC, CCCB
    // BCBC, BCCB, CBCB
    // AAAC, AACA, ACAA, CAAA
    println(new ProblemSolverz(3).ways(4))

    // a LOT of ways
    println(new ProblemSolverz(3).ways(20))
  }
}

class ProblemSolverz(k: Int) {
  def ways(N: Int) =
    // number of states in which
    // A solved a number of problems equal to 0 in modulo k,
    // C solved at least one problem,
    // B whatever
    states(N - 1)((0, 0, 1)) + states(N - 1)((0, 1, 1))

  val states = makeNextStates(Map((0, 0, 0) -> 1L)) // initial state

  def makeNextStates(previousStates: Map[(Int, Int, Int), Long]): Stream[Map[(Int, Int, Int), Long]] = {
    // initialize all states to 0 (makes for cleaner code later)
    val states = scala.collection.mutable.Map((for {
      a <- 0 until k
      b <- 0 to 1
      c <- 0 to 1
    } yield ((a, b, c), 0L)): _*)

    // for each previous state, compute its successors
    previousStates.foreach({
      case ((a, b, c), ways) => {
        // A could solve this problem
        states(((a + 1) % k, 0, c)) += ways
        // B could solve this problem, if he is rested
        if (b == 0)
          states((a, 1, c)) += ways
        // C could solve this problem
        states((a, 0, 1)) += ways
      }
    })

    // contribute this state to the stream
    Stream.cons(states, makeNextStates(states))
  }
}
$\endgroup$
  • $\begingroup$ Now that I got at this point, I'm curious about the application of this. Did I just solve some DNA analysis problem? $\endgroup$ – djjeck Dec 10 '14 at 2:51

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.