Koza Nostra#5103

Koza Nostra (Editorial)

Let $g (n)$ be the number of ways to deal cards to $n$ teachers arranged in a line (the first and the last are not considered adjacent). This problem is equivalent to counting binary sequences of length $n$ consisting of $0$ s and $1$ s in which no two $1$ s are adjacent. The solution is given by the Fibonacci sequence defined by the following recurrence relation:

g (n) = ⎩ ⎨ ⎧ 2, n = 1, 3, n = 2, g (n - 1) + g (n - 2), n \geq 3.

g(n)= \begin{cases} 2, n = 1, \\ 3, n = 2, \\ g(n - 1) + g(n - 2), n \ge 3. \end{cases}

Let $f (n)$ be the number of ways to deal cards to $n$ teachers seated in a circle.

If the first teacher does not receive an ace, then the remaining $n - 1$ n - 1 teachers can be dealt aces in $g (n - 1)$ g(n - 1) ways.
If the first teacher does receive an ace, then the second and the last teachers must not receive aces. In this case, the remaining $n - 3$ n - 3 teachers can be dealt aces in $g (n - 3)$ g(n - 3) ways.

Thus, we obtain the following relation:

f (n) = g (n - 1) + g (n - 3), i f n \geq 3

f(n) = g(n - 1) + g(n - 3),~if~n \ge 3

Example

For $n = 3$ n = 3, we need the value $g (0)$ . It can be found from the equality $g (0) + g (1) = g (2)$ g(0) + g(1) = g(2), which gives

g (0) = g (2) - g (1) = 3 - 2 = 1

g(0) = g(2) - g(1) = 3 - 2 = 1

Therefore,

f (3) = g (2) + g (0) = 3 + 1 = 4

f(3) = g(2) + g(0) = 3 + 1 = 4

The base cases are as follows:

f (1) = 2 f (2) = 3

f(1) = 2 \\ f(2) = 3

Algorithm implementation

Declare an array $f ib$ to store the Fibonacci numbers.

#define MAX 46
int fib[MAX];

The main part of the program. Compute the Fibonacci numbers.

fib[0] = 1; fib[1] = 2;
for (int i = 2; i < MAX; i++)
  fib[i] = fib[i - 1] + fib[i - 2];

Read the input number $n$ .

scanf("%d", &n);

Compute the answer $r es$ .

if (n == 1) res = 2; else 
if (n == 2) res = 3; else
res = fib[n - 1] + fib[n - 3];

Print the answer.

printf("%d\n", res);

Java implementation

import java.util.*;

public class Main 
{
  private static final int MAX = 46;
  public static void main(String[] args) 
  {

Java

Declare an array $f ib$ to store the Fibonacci numbers.

    int[] fib = new int[MAX];

Compute the Fibonacci numbers.

    fib[0] = 1;
    fib[1] = 2;
    for (int i = 2; i < MAX; i++)
      fib[i] = fib[i - 1] + fib[i - 2];

Read the input number $n$ .

    Scanner con = new Scanner(System.in);
    int n = con.nextInt();

Compute the answer $r es$ .

    int res;
    if (n == 1) res = 2;
    else if (n == 2) res = 3;
    else res = fib[n - 1] + fib[n - 3];

Print the answer.

    System.out.println(res);
  }
}

Python implementation

Declare a list $f ib$ to store the Fibonacci numbers.

fib = [0] * 46

Compute the Fibonacci numbers.

fib[0] = 1
fib[1] = 2
for i in range(2, 46):
  fib[i] = fib[i - 1] + fib[i - 2]

Read the input number $n$ .

n = int(input())

Compute the answer $r es$ .

if n == 1: res = 2
elif n == 2: res = 3
else: res = fib[n - 1] + fib[n - 3]

Print the answer.

print(res)