1
$\begingroup$

Say you have one bag of apples and one bag of oranges. Each bag contains at least one fruit, and the number of fruit in each bag is an odd number.

I have found that it is impossible to line up these fruit together in a way that is identical forwards and backwards. In other words, there exists no "symmetric" sequence.

Example: 3 Oranges, 1 Apple

[symmetry impossible]
A O O O
O A O O
O O A O
O O O A

However if we require any one of the bags (or both) to contain an even number of fruit, symmetry is always possible.

Example: 3 Oranges, 2 Apples

[symmetry possible]
A A O O O
A O A O O
A O O A O
A O O O A
O A A O O
O A O A O
O A O O A
O O A A O
O O A O A

I was wondering, is there a proof for why this is?

$\endgroup$
2
  • $\begingroup$ Instead of apples and oranges, you can also think of these as letters of a word. Then your "symmetric arrangement" would be known as a palindrome. $\endgroup$
    – JRN
    Oct 3, 2014 at 6:11
  • $\begingroup$ If you're interested in these types of problems, then you might want to take a look at combinatorics on words. $\endgroup$
    – JRN
    Oct 3, 2014 at 6:30

1 Answer 1

3
$\begingroup$

Let an alphabet consist of two letters: $a$ and $b$. We're looking for words formed from this alphabet that result in palindromes (words that read the same forwards and backwards, that is, the word $w$ is a palindrome if it is the same as its reversal $w^R$).

A palindrome can contain either an even number of letters (for example, $abbbba$) or an odd number of letters (for example, $ababa$).

In the case where the palindrome has an even number of letters, note that the first half of the palindrome has exactly the same number of letters of each type as the last half (for example, the first half of $abbbba$ has one $a$ and two $b$'s, the second half also has one $a$ and two $b$'s). Thus, the palindrome must have an even number of each type of letter ($2\times 1=2$ instances of $a$'s and $2\times 2=4$ instances of $b$'s).

In the case where the palindrome has an odd number of letters, note that we can express the palindrome as $xyx^R$, where $x$ is a word, $x^R$ is the reversal of $x$, and $y$ is a letter. (For the palindrome $ababa$, $x=ab$, $x^R=ba$, and $y=a$.) The letter frequencies of $x$ and $x^R$ are the same; thus the letter frequencies for $xx^R$ are both even. But since there is an extra letter $y$, then one of the letters has to have an even letter frequency while the other letter has to have an odd letter frequency.

$\endgroup$
1
  • 1
    $\begingroup$ You're a genius, bravissimo. $\endgroup$ Oct 3, 2014 at 6:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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