Challenge Level

Jaeyoon from 숲속초등학교 (Forest Elementary School) in South Korea sent in the following:

Let's do this in general. Suppose you want as many kids as possible to at some flavour(s) from the ice-cream cafe and there are x flavours. What is the maximum number of kids that they can all eat ice-cream, so that nobody has exactly the same combination of other kids?

Let's first find out the pattern. Let's say there is one flavour: A. Directly, you can see there are 2 possibilities: Eat A, Do not eat A. But not eating A means eating nothing in this case. So, only Child 1 can eat ice-cream: Flavour A.

Now, let’s say there are two flavours: A and B. Then, Child 1 could eat A and B, Child 2 eats A, and Child 3 eats B. The next child, Child 4 can't eat anything. So, there are three possible ways for two flavours.

As we saw, there are seven ways from three flavours. And although it might take some time, there are 15 ways for four flavours.

1, 3, 7, 15.... Let's compare this with this sequence, starting from 2, doubling every time (these numbers in the sequence are known as powers of 2): 2, 4, 8, 16.... You can see that the terms in the first sequence are one less than the second. The numbers 1, 3, 7, 15... has a special name; Mersenne numbers. And the way to generate them is to multiply 2 by itself x times, then subtract 1.

This Ice Cream problem is related with the power set. A power set is all possible distinct ways that you can have some object(s). This includes the empty set, which has no objects. And the power set of x objects is 2 multiplied by itself x times, thus, 2 to the xth power. But since we are ignoring the empty set, there are 1 fewer than 2 to the xth power ways for x flavours, which are the Mersenne numbers.

(If you want to you can find out more about these Mersenne Numbers here https://primes.utm.edu/mersenne/)

Alex and India from St Blaise School Abingdon wrote:-

We chose to do the option with four ice creams and worked our way down like a, b, c, d then a, b, c next a, b, d and so on. If you are correct you should have had fifteen people in your shop. Good Luck!

Shafiq from Beckford Primary School Camden wrote:-

We have found out that the maximum number of children who could have ice-cream was seven:

ABC, AB, CB, CA, C, A, B

What would happen if we have more flavours?

We have found out that if we have four flavours, 15 children could have ice-cream.

If we have five flavours, 31 children could have ice-cream.

We saw a pattern; each time we added a flavour, the number of children that could have ice-cream was multiplied by two, plus one more.

Cameron from the Twyford School sent in the following:-

A, B and C cannot be switched with another combination because one combination (A, B and C) will not be allowed, that will mean there will only be six combinations.

This is why I think that there will not be another possible combination according to the rules. Otherwise there would be lots more combinations than one. Here is an example:

ACB, BA, CA, CB, A, B, C

The only combination is:

ABC, AB, AC, BC, A, B, C

Although you can change the order in which the children eat the ice cream combinations, the combinations themselves essentially stay the same.

Alfie from St Aidan's Primary School wrote:

This is how many different permutations there are for all seven children getting ice cream.

We approached the problem using a basic structure:

Number of Flavours | Combinations of Flavours | |

Part 1 | 3 | abc |

Part 2 | 2 | ab |

" | 2 | bc |

" | 2 | ca |

Part 3 | 1 | a |

" | 1 | b |

" | 1 | c |

Part 1 must remain abc because it contains every other order. Parts 2 and 3 both have six permutations each

Part 2: ab,bc,ca; ab,ca,bc; bc,ab,ca; bc,ca,ab; ca,ab,bc; ca,bc,ab

and

Part 3: a,b,c; a,c,b; b,c,a; b,a,c; c,b,a; c,a,b.

This means that for each possible permutation of part 2, there are 6 permutations of part 3, so in total there are 6 x 6 permutations for the basic structure meaning 36 in total.

The issue with this is that there is another, more complex structure which obeys the rules:

Number of flavours | Combination of Flavours | |

Part 1 | 3 | abc |

Part 2 | 2 | ab |

" | 2 | ac |

" | 1 | a |

Part 3 | 2 | bc |

" | 1 | b |

" | 1 | c |

This works almost exactly as the previous structure except now the 5th choice is decided by part 2.

Part 2 has 6 combinations {ab,ca; ca,ab; ab,bc, bc, ab; ca,cb; cb,ca}

Part 3 has 2 combinations, the two different orders for the remaining single flavours of ice cream.

Therefore the total number of permutations for this structure is 6 x 2 = 12

To get the total number of permutations across both structures we have:

36 (the number of permutations for the basic structure) + 12 (the number of permutations for the complex structure) = 48

Well done! Some very thorough examplanations here. We look forward to hearing more from you all.