in Combinatory
1,160 views
1 vote
1 vote
Anand is preparing a pizza with 8 slices, and he has 10 toppings to put on the pizza. He can put only one
topping on each slice but can use the same topping on zero or more slices. In how many unique ways can
he prepare the slices so that the same topping is not used in adjacent slices?
in Combinatory
1.2k views

2 Comments

It is similar problem. put n from 1 to 8 and  C from 1 to 10 and fill the values in the table using recurrence.
0
0

3 Answers

1 vote
1 vote

Let f(n) be the number of ways to color a cycle graph of n nodes using k colors.

Suppose if we have only 2 nodes and k colors, f(2) = k*(k-1)

Similarly, f(3) = k(k-1)(k-2).

Now lets find the recurrence relation for f(n).

First node can be colored in k ways.

Second node can be colored in (k-1) ways.

Similarly third, fourth,..., last node can be colored in (k-1) ways.

So

But the last and first nodes can be the same color, we need to remove those arrangements.

Now merge the first node and last node as one node.

Now the number of ways to color (n-1) nodes using k colors is f(n-1)

So the recurrence relation is

When n is even,

a = k-1, r = -(k-1)

When n is odd,

a = -(k-1), r = -(k-1)

Coming to our problem, n = 8 and k = 10.

$$f(8) = 9*(9^7+1)=43046730$$

4 Comments

edited by

@venkatesh pagadala

for f(1),f(2) and f(3) the equations are correct but f(4) is not following the constraint.

case1.

if A,B,C,D are the consecutive nodes in rectangle then  A can be coloured using k colours.(say blue)

B can be coloured using k-1 colours.(say green)

C can be coloured using k-2 colours(say blue)

D can be coloured using k-1 colours(say red)

 

Case 2.

if A,B,C,D are the consective nodes in rectangle then

A can be coloured using k colours.(say blue)

B can be coloured using k-1 colours.(say green)

C can be coloured using k-2 colours(say pink)

D can be coloured using k-2 colours(say red) here k-2 because they we can't use blue and pink.

 

You have just eliminated the cases where first and last nodes can't have same color but these cases are not eliminated.

0
0
I have eliminated those cases by subtracting f(n-1) from f(n)
0
0
So for filling a rectangle with $10$ colors the answer should be

$f(4) = 9*(9^3 -1)=6552$ right ?
0
0
No.

here n is even, so answer would be $$9*(9^3+1)=6570$$
1
1
0 votes
0 votes
For the slice, he has 10 choices. For the second he has nine choices. For the third, he has nine choices(Think why).....Similarly, for the rest of the slices, there are 9 choices, for the last one he has 8 choices.

Therefore the number of ways this can be done$=10*9*9*9*9*9*9*8=10*9^{6}*8=42515280$
edited by

4 Comments

sir why cant it be 10*9*10*9*10 soon? till 8 slices..as we can say that 1st and 3rd can have same toppings.
0
0

@Sainath Mandavilli

say you select $T_1$ for $1^{st}$ slice among the given 10 toppings.

then we can have $9$ choices for second slice i.e.  $T_2,T_3, .....T_{10}$ and you selected $T_2$

So for $3^{rd}$ slice we can have  $T_1, T_3,T_4....T_{10}$ i.e. 9 choices only... not 10 since we can't use $T_2$ here.

 

0
0
what about the last piece?

It is adjacent to two pieces right. So, there are only 8 choices for the last one

number of ways = 10*9*9*9*9*9*9*8 = 42515280
2
2
yes correct.
0
0
0 votes
0 votes

Not a correct approach but still gives correct answer.

Total number of ways to fill $10$ toppings in $8$ slices = $10^8$

If any two slices have same topping then they are invalid

So the number of invalid cases can be founded as follows

int main(void) 
{
	
  int Slice_1_color,Slice_2_color,Slice_3_color,Slice_4_color,Slice_5_color,Slice_6_color,Slice_7_color,Slice_8_color;
  long long int invalid_cases;
  invalid_cases=0;
  for(Slice_1_color=1;Slice_1_color<=10;Slice_1_color++)
   for(Slice_2_color=1;Slice_2_color<=10;Slice_2_color++)
    for(Slice_3_color=1;Slice_3_color<=10;Slice_3_color++)
     for(Slice_4_color=1;Slice_4_color<=10;Slice_4_color++)
      for(Slice_5_color=1;Slice_5_color<=10;Slice_5_color++)
       for(Slice_6_color=1;Slice_6_color<=10;Slice_6_color++)
        for(Slice_7_color=1;Slice_7_color<=10;Slice_7_color++)
         for(Slice_8_color=1;Slice_8_color<=10;Slice_8_color++)
         {
           if( ( Slice_1_color==Slice_2_color)||( Slice_2_color==Slice_3_color)||( Slice_3_color==Slice_4_color)||( Slice_4_color==Slice_5_color)||( Slice_5_color==Slice_6_color)||( Slice_6_color==Slice_7_color)||( Slice_7_color==Slice_8_color)||( Slice_8_color==Slice_1_color))
             invalid_cases++;
         }
   printf("invalid cases = %lld",invalid_cases);
 
	return 0;
}

 Using the above code we get the invalid cases = $56953270$

$\therefore$ $Valid\ cases =\ Total\ cases\ -\ Invalid\ cases = 10^8 - 56953270$ = $43046730$

edited by

4 Comments

edited by
..
0
0
Ok, but are you sure that the inclusion-exclusion principle is valid when we are considering adjacent pairs in a circular fashion? The last two don't seem convincing because seven adjacent pairs and eight adjacent pairs are the same.
0
0
Im sure that inclusion-exclusion will be used but how that is little confusing

7 adjacent and 8 adjacent pairs are same that's why i have not used the pair logic. instead i have selected as groups . pair,triplets,quads...octates.
0
0