1,719 views
1 votes
1 votes
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?

3 Answers

1 votes
1 votes

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$$

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
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

Related questions

1 votes
1 votes
0 answers
1
Sayan Bose asked Oct 25, 2018
2,490 views
1 votes
1 votes
0 answers
2
o asked Apr 29, 2022
427 views
In this won’t A and C both be correct answers as A can be obtained by considering only central part of C?Also, I tried this by brute force by putting some values; is th...
1 votes
1 votes
2 answers
3
Hakuna Matata asked May 3, 2018
793 views
Number of distinct simple graphs possible, given 8 vertices and not considering self loops?
2 votes
2 votes
1 answer
4
Hakuna Matata asked May 3, 2018
1,161 views
There are 12 pair of shoes, what is the probability that atleast one complete pair of shoes are present if 4 shoes are selected at random?