For Questions B and C please PROVE that it is the optimal result.

Suppose x is a positive integer. The (imaginary) sea of Babab has islands each of which has an x-letter name that uses only the letters a and b, and such that for each x-letter name that uses only the letters a and b, there is an island. For example, if x = 3, then Aaa, Aab, Aba, Baa, Abb, Bab, Bba and Bbb are the islands in the sea of Babab. The transportation system for Babab consists of ferries traveling back and forth between each pair of islands that differ in exactly one letter. For example, there is a ferry connecting Bab and Bbb since they differ only in the second letter.

Count the ferry route for both directions as a single ferry route, so for example, the ferry from Bab to Bbb is the same ferry route.

Babab does not have much in the way of natural resources or farm land so nearly all food and supplies are provided by the Babab All Bulk Company (BABCO). The people of Babab (Bababians) desire easy access to a BABCO store, where easy access means there is a BABCO store on their own island or on one that they can get to with a single ferry ride. However, BABCO finds it uneconomical to give the people on one island easy access to two different BABCO stores, and BABCO is willing to deny some Bababians easy access to a BABCO store in order to meet this restriction.

b) In the cases x = 3, x = 4, and x = 5, what is the maximum number of stores that BABCO can build while satisfying the restriction than no one has easy access to more than one BABCO store? Be sure to PROVE your answer is optimal.

c) Now suppose BABCO changes its strategy and decides it wants to be sure every Bababian has access to a BABCO store even if it means some Bababians have easy access to two stores. What is the minimum number of stores needed to satisfy this condition in the cases x = 3, x = 4, and x = 5?

d) Can you find optimal solutions to parts b and c for x = 6?