Problem of the Month - February 2010 : Strings

If a string s with n unique letters can be rearranged such that none of the letters end up in their original positions, such a rearrangement is called an proper orientation of s. Consider, for example, the string "DOG" has the following proper orientations:

• GDO
• OGD

Now, let A_n denote the number of unique proper orientations of a string s of length n. It should be fairly clear that A₁=0 and A₂=1; also, assume A₀=1.

• 1. Determine A₃ and A₄.
• 2. Determine a recursive relationship in the sequence A.

[Solution]

Problem of the Month - March 2010: eCoins

The expected value of an event or value with a given probability distribution is equal to the weighted average of the expected outcomes, weighted by probability. For example, if there is a 1/3 chance of catching 4 red balls and there is a 2/3 chance of catching 5 red balls, the expected number of red balls that will be caught is the sum of 1/3 of 4 and 2/3 of 5.

Given this defininition of expected value, consider each of the following:

1. A coin is flipped until a heads appears. Determine, with justification, the expected number of times the coin will be flipped.
2. A die is rolled until a composite number appears as its top face. Determine the expected number of times the die will be rolled.

Finally, if you're willing to give it a shot, here's a more challenging problem:

3. A coin is flipped until two consecutive heads appear. Determine the expected number of times the coin will be flipped.

Problem of the Month - April 2010: Subsets

In this problem we examine the number of subsets a given set might have. The set A is said to be a subset of the set B if all elements of A are elements of B. Another way to think of this is to think of one set as being "contained" by another, or "included" in the greater set. Similarly, a superset of a given set is one which "includes" all elements of its respective subset. For example, the set {1,2} is a subset of of the set {1,2,3}. By notation, a proper subset of a set B is one that is a subset of B but is not equal to B. Also, note that the null (empty) set, denoted { }, is a subset of all sets except itself.

• Determine the number of distinct subsets of the set {0,1,2} (remember the empty set!).
• Determine the number of distinct subsets of a set with n distinct elements.
• How many subsets of {{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}} satisfy the property that the union of each of the elements of the set forms the set {1,2,3,4}?

Problem of the Month - June 2010: S-S-S-Sum!

For a given set A, let the S-value of A denote the sum of the odd-numbered elements (1st, 3rd, 5th, etc.) minus the sum of the even-numbered elements (2nd, 4th, etc.) after A has been sorted in non-increasing order; in otherwords, alternate numbers are added or subtracted from the total sum. For example, the S-value of {1,4,6,4,8,3,7} is the S-value of {8,7,6,4,4,3,1} = 8 - 7 + 6 - 4 + 4 - 3 + 1 = 5.

For all proper subsets of {1,3,5,7,9}, there exists a positive S-value associated with the subset. Determine the sum of the S-values of all of these subsets.