Dark Mode

Chaitrasj
asked
in Combinatory
Mar 11, 2019

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

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?

1

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.

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

edited
Jul 6, 2019
by Satbir

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

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

0

0

2

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$

0