This is a problem that appeared in Algorithmic engagements 2007 and discussed by Kubica and Radoszewski 

The problem statement: 

An anti-binary set is a set of integers that does not contain two numbers of the form m and 2m. For example, the set: 

A = {2, 3, 5, 8, 11, 13} 

is anti-binary whereas the set: 

B = {2, 3, 5, 6, 8, 11, 13} 

is not, since both 3 and 6 are its elements. 

What is the largest size of an anti-binary set that is a subset of 

1. {1, … , 11} 

2. {1, … , 12} 

3. {1, … , 13} 

4. {1, … , 14} 

5. {1, … , 15} 

How many different anti-binary subsets of the same size exist? 

The Solution: 

In this case a graph like this helps: 

1 --> 2 -->4-->8 

               3-->6-->12 

                5-->10 

              7 9 11 13 

Where --> denotes an edge when elements are connected by the relation m-->2m 

The elements that don’t connect are mentioned last. 

We can select all of the elements in the last row, one element from the second last row, the first and the last element from the second row and alternate elements from the first row giving us the cardinality of 9. 

More generally, let us say that for a path of size n, the number of anti-binary subsets is An. Then the number of all anti-binary subsets of the given sequence is A1 power 4 times A2 power 1 times A3 power 1 and A4 power 1 by permutations. A1 = 2 and A2  = 3 because we say whether those anti-binary element or its combination is included or not. 

Since the pattern of picking the anti-binary set is that of picking alternate elements in the series m[Symbol]2m, we say that if an anti binary set contains the last element, it does not contain its predecessor.  Hence the number of such sets equals An-2. Given that the last element can be included or not, we establish an optimal substructure as An = An-1 + An-2 

And hence a recursive relation where A1 = 2 and A2 = 3. 

This therefore is the Fibonacci series where An = Fibonacci(n-2) 

int Fibonacci(int n)  {  

if (n <= 0 ) return 0; 

 int value = Fibonacci(n-1) + Fibonacci(n-2);  

return value;  

} 

And we can count all the subsets as follows: 

AllAntiBinarySets(A, n)  

If n == 0   Return 0  

q = 1  

int r = n %2 == 0 ? n: n+1 

For k = I to log(r) 

     If (graph-exists(A,k)) 

            q *=  Fibonacci(k)*numberofGraphs; 

  return q 

 

 

 

  

 

This is a discussion of an Olympiad problem from Kubica and Radozewski: 

Problem statement: 

You are given coins with the values being powers of two. 1,2,4,8,16,32,… and you have exactly one coin of each value. Then you could pay any (positive integer) amount of money using these coins(for example, 45 = 1 + 4 + 8 + 32) 

What is the smallest amount of money, which cannot be paid using the following set of coins: 

1. 6, 3, 2, 10, 21, 46, 1, 48? 

2. 12, 7, 3, 2, 31, 27, 28, 1? 

3. 27, 56, 1, 13, 60, 4, 7, 2? 

4. 44, 39, 5, 1, 9, 1, 18, 2? 

5. 62, 3, 26, 12, 53, 2, 1, 7? 

You have exactly one coin of each kind. 

Solution: 

The first step is to sort the sequence of coins in a non-decreasing order, for the sequence in the first subtask we have: 

1. 1,2,3,6,10,21,46,48 

Using the first two coins we can pay any integer amount from [1,3]. With the first three, we can pay any amount from [1,6] With the first four, we can pay any amount from [1,12] Note that for any amount 1-6 we do not have to use the last coin in the current sequence and for amount higher than that we have to use the last coin. 

In general, if the range of amounts that can be paid using the first k coins is from 0 to r, and the following coin has value x, then either: 

• x <= r+1 and it is possible to pay any amount from 0 to r +x using the first k +1 coins, or 

• x > r + 1 and it is not possible to pay the amount of r + 1, since x and all the following coins have greater values. 

Using this observation, we obtain the following sequence of included coins and ranges of amounts that can be paid: 

Coins                        1    2    3    6    10    21    46    48     

Maximum amount 1   3    6    12  22    43     

The amount 44 cannot be paid. 

The approach here is also dynamic programming although the strategy above uses greedy choice We generate all the subsequences of a given non-empty prefix and divide it into two groups: those containing the last element of the prefix and those not containing it. 

MaxSumUnPaid(Coins, I, j) 

If len(Coins) == 1 

   Return Coins[0]  

m[i,j] = 0  

For k = 0 to j-I-1 

     if (jth coin <= MaxSumUnPaid(Coins Choose K, I,j-1)  

           q =   MaxSumUnPaid(Coins Choose K, I,j-1) + MaxSumUnPaid(Coins with jth coin only, j,j) 

     If q > m[I,j]  

             M[I,j] = q  

  return m[I,j]

This is a discussion of another Olympiad problem on Informatics:

Question:

We are given 11 line segments of the following lengths:

(a)    1, 49, 11, 3, 338, 128, 30, 78, 17, 208, 6

(b)   103, 1, 15, 8, 167, 271, 5, 3, 64, 25, 38

(c)    94, 154, 5, 8, 248, 35, 2, 1, 58, 23, 13

(d)   87, 3, 20, 12, 141, 4, 228, 52, 1, 33, 8

(e)   108, 25, 178, 15, 3, 42, 9, 68, 1, 4, 286

Is it possible to pick three different line segments from the set and use them to obtain a triangle with positive area? If so, which three segments to choose?

Solution: A triangle is formed when we choose segments such that the longest segment is strictly shorter than the total length of the smaller two. Say a + b > c

In each of the above we can pick three segments that suit this condition and can be used to form a triangle and these solutions are:

(a)    30, 49, 78

(b)   15,25,38

(c)    13,23,35

(d)   20,33,52

(e)   42,68,108

Notice if we arrange the lengths of the segments in sorted order, we only have to progress until we meet the criteria above. For example,

(a)    1,3, 6, 11, 17, 30, 49, 78, . . .

We progress picking consecutive three until we pick 30, 49 and 78.

In other words the algorithm for this task involves a greedy strategy. The greedy choice property is justified with the following: we start with three segments in sorted order and show that by increasing the lengths of the smaller two (without exceeding the lengths of the longer one) we limit the available choices and raise the odds of obtaining a solution.

Hence we can write the solution as:

PickThree(Segments, I,j)

SortSegments(Segments)

for k =  I+2 to j

   if Segments[k-1] + Segments[k-2] > Segments[k]

        return Segments[k-2], Segments[k-1], Segments[k]

return null