Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Carlo has six apples and six pears: how many ways he can set in a row 6 fruits so that there should never be a pear between two apples?

Thanks in advance to everyone who will help me resolving this problem.

share|improve this question
    
@Asaf (view edits) Great minds think alike! –  amWhy Nov 22 '12 at 15:03

2 Answers 2

There is some potential ambiguity in the problem. Is it that there is (1) no pear directly between two apples, or (2) is for example APPAAA also forbidden? We take interpretation (1).

The solution below is ugly. We list all the possibilities, and then count them.

But we will take a few shortcuts. There are $2^6$ six-letter "words" using the letters A and/or P. We ask how many of these words are forbidden.

(i) Certainly all words of shape APAXYZ are forbidden. There are $2^3$ of these.

(ii) All words of shape XAPAYZ are forbidden. There are $2^3$ of these.

(iii) Now we look at words of the shape XYAPAZ. Here there is a complication, since APAPAZ has already been counted in (i). Thus there are $3$ choices for XY, and for each there are $2$ choices for Z, a total of $6$.

(iv) Finally we look at XYZAPA. Of the $8$ choices for XYZ, the choice APA has already been counted in (i). And the choices XAP have been counted in (ii). This leaves $5$ choices.

So there are $27$ forbidden configurations, and therefore the number of allowed configurations is $64-27$.

Another way: Instead of the cases analysis, we can use the Principle of Inclusion/Exclusion to count the forbidden configurations.

So we count the words that contain the sequence APA. Think of this as a new letter N. For any sequence XYZ made up of A and/or P, there are $4$ places where we can put the N, for a total of $32$. But we have counted APAAPA twice, as well as XAPAPA and APAPAZ. So $5$ forbidden configurations have been double-counted. It follows that there are $32-5$ forbidden configurations.

A little smoother, but the added level of sophistication may be overkill for $n=6$. For $n$ of size greater than $6$, one should probably bring in the heavier machinery.

share|improve this answer
    
Thanks for the reply Andrè. Yes, I meant the first case you pointed out. –  Snowzurfer Nov 22 '12 at 18:26

The following is an approach different from André's; it allows of rows of arbitrary length.

Let $L$ be the set of finite $\{A,P\}$-strings that do not contain $APA$ as a substring. Denote by $x_1(n)$ the number of strings in $L$ of length $n$ ending with $A$, by $x_2(n)$ the number of such strings ending with $AP$, and by $x_3(n)$ the number of such strings ending with $PP$. Then $$x_1(2)=2\ ,\quad x_2(2)=1\ ,\quad x_3(2)=1\ .$$ Given that substrings $APA$ are forbidden we have $$\eqalign{ x_1(n+1)&=x_1(n)+x_3(n)\ , \cr x_2(n+1)&=x_1(n)\ , \cr x_3(n+1)&=x_2(n)+x_3(n)\ ,\cr}$$ or $${\bf x}(n+1)=T {\bf x}(n)\qquad(n\geq2)\ ,$$ where $T$ is the matrix $$T=\left[\matrix{1&0&1\cr 1&0&0\cr 0&1&1\cr}\right]\ .$$ It follows that $${\bf x}(n)=T^{n-2}\left[\matrix{2\cr1\cr1\cr}\right]\ .$$ Unfortunately $T$ has unfriendly eigenvalues, so its difficult to express arbitrary powers of $T$. Using Mathematica we obtain $${\bf x}(6)=T^4\left[\matrix{2\cr1\cr1\cr}\right]=\left[\matrix{16\cr9\cr12\cr}\right]\ .$$ Therefore the number of allowed strings of length $6$ is $37$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.