[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.


1. Cardinality

Prove or disprove: For any sets A and B, if |A| = |B|, then |℘(A)| = |℘(B)|.

2. A population problem

King Dorgon the Mighty, sole overlord of the Kingdom of Dorgonia, decrees that to prevent confusion, all persons in his kingdom will be given unique names. Furthermore, each name must be of the form CVCCVC or VCVCVC, where V represents an element of the 6-element set {a,e,i,o,u,y} and C represents an element of the 21-element set {b,c,d,f,g,h,j,k,l,m,n,p,q,r,s,t,v,w,x,z,y} (note that the letter y appears in both sets).

For example, the King Dorgon's privy counselors Lodwuj, Yutkis, Qabwyb, and Dimtim all have names that follow the first pattern, his personal guards Ozojiv, Utamak, Uqudaw, and Ebijyj all have names that follow the second pattern, but his disgraced and exiled half-brother Snfrtz the Usurper doesn't follow either pattern.

Assuming that King Dorgon's plan is successful, what can you say about the population of Dorgonia?

3. Six-fingered poker

A standard American poker deck consists of 52 cards, which we can think of as elements of the set {♠,♡,♢,♣}×{A,2,3,4,5,6,7,8,9,10,J,Q,K}; the first component gives the suit of the card and the second gives its rank. In the game of six-fingered poker, each player is dealt a hand of six cards, and looks to see if they have a hand that meets one of the following criteria:

At least four of the cards have the same suit.
At least three of the cards have the same rank.
Triple plumbing explosion
A hand that is both a four-flush and three-of-a-kind.

Note that unlike in standard five-card poker, it is possible for the same hand to satisfy multiple criteria: an instance of a triple plumbing explosion is still an instance of three-of-a-kind.

Assuming the order of the cards doesn't matter, how many different ways are there to form each type of hand?

2014-06-17 11:57