Homework/Forum problems from Math 5020 FW07-08

Problem list

The first week (September 20, 2007) I suggested that you do 3-4 induction problems from section 1.1 #1-18

Problems that I assigned for the forum and for homework:

Section 1.1 #9,10,16,17
Section 1.2 #3,4
Section 2.1 #6
Section 2.2 #4, 7, 10
A. 1^4 + 2^4 + 3^4 + ... + n^4 = (6*n^5 + 15*n^4 + 10*n^3 - n)/30
B. 1^3 + 3^3 + 5^3 + ... + (2n-1)^3 = n^2(2n^2-1)
section 1-1 #15
section 3-1 #3, 12*, 13, 14
C. How many ternary sequences (using the numbers 0,1,2) are there without any consecutive digits the same?
D. How many ways are there of rearranging the letters of the word CONSONANTS?
E. How many 5 card hands have at least one card from each suit?
F. How many 5 card hands have exactly 2 pair?
G. How many 5 card hands have exactly one 3-of-a-kind (no 4-of-a-kind or full house)?
H. How many 5 card hands have exactly 1 pair (and no poker hand higher)?
I. How many ways are there of rearranging the letters of the word INQUISITIVE such that a U does not follow a Q?
J. How many 5 card hands are there such that there are the same number of hearts as spades?
K. How many committees can be formed from 4 men and 6 women with 4 members, two of whom are women and Mr. and Mrs. Baggins cannot both be on the committee?
L. What is the number of 5 die rolls such that only two different values appear?
M. Show p|(n^(p^r)-n)
O. A student union has 8 gr.12 students, 6 gr.11 students, 3 gr.10 students and 2 gr.9 students. How many different choices for pres/VP/treasurer are there such that the president is from gr.11 or gr.12 and the treasurer is from gr.9 or gr.10?
P. How many different values of non-negative integers x,y,z are there such that x+y+z = 20?

4-2 #3
Q. In a poker game (Texas hold 'em) at a point in the game, two cards are delt face up that are shared by all the players. There are three other cards which will complete the hand. Given that the 10H and 10D are showing, how many cards will complete this hand to something better than a pair? (you need to know the rankings of poker hands)
R. In the lottery 6/49, 6 numbers are chosen from 1 to 49 plus a bonus number. For a given set of winning numbers, how many possible tickets are there that match 4 numbers and the bonus?
S. How many collections of non-negative integers are there x,y,z such that x+y+z<=20
T. Let S(n,3) = the number of ways of splitting a set containing n elements into three subsets = the number of ways of putting n distinguished things in 3 unlabled boxes such that no box is empty. Show S(n,3) = 3 S(n-1,3) + 2^(n-2) - 1. Example: S(3,3) = 1 because {1},{2},{3} is the only splitting of {1,2,3} into three subsets. S(4,3) = 6 = 3*S(3,3) + 2^2 -1 because {{1,2}, {3},{4}} - {{1,3},{2},{4}} - {{1,4},{2},{3}} - {{1},{2,3},{4}} - {{1},{2,4},{3}} - {{1},{2},{3,4}} are the 6 ways of splitting {1,2,3,4} into three subsets.
U. How many ways are there of selecting 5 marbles from a group of 5 red marbles, 4 blues and 3 yellows?
V. Let B(n) be the number of ways of putting n labeled balls in to n indistinguishable boxes. Show that B(n) = B(0) C(n,0) + B(1) C(n,1) + ... + B(n-1) C(n,n-1)
W. How many ways are there of splitting the set of integers {1, 2, 3, ..., 10} into three disjoint subsets each of which are of even size?
X. How many ways are there of distributing n identical balls into 6 boxes so that the first two boxes have collectively at most four balls?
Y. How many ways are there of taking a collection of 12 apples from four different types so that there are at least 2 apples of each type?
Z. How many 2x2 invertible matrices are there mod 29 (you are looking for matrices [[a,b],[c,d]] such that ad - bc is not 0 (mod 29)?
AA. How many 2x2 matrices are there such that a d - bc = 1 (mod 29)?
BB. How many election outcomes are possible if there are 3 candidates and 30 voters?
CC. How many election outcomes are possible if there are 3 candidates and 30 voters such that there is at least one candidate that receives a majority of the votes?
DD. How many ways are there rearranging the letters of the word TELECONFERENCE such that there are no consecutive E's?
EE. What is the number of ways of arranging 10 of the letters a,b,c,d such that there are the same number of a's as b's and the a's are not consecutive?
FF. 5-2 #11
GG. 5-2 #12
HH. 5-2 #23
II. Find the number of words of length n in 3 letters {a,b,c} with an even number of a's such that the words are strictly smaller in dictionary order than (we say `strictly lexicographically smaller than') all possible cyclic shifts of 1 through n-1 (cyclicly shifting n times gets you back to the original so we don't count it). First do this for n=0,1,2,...,6 (or possibly higher). Next try to find a general formula if possible.
Example 1: the cyclic shifts of aab are aba, baa. We have that aab is strictly smaller than the both aba and baa.
Example 2: aabaabccaca is not the lexicographically smallest of all of its cyclic shifts because aaabaabccac is smaller in dictionary order.
Example 3: aabaab has cyclic shifts of abaaba, baabaa, aabaab, abaaba, baabaa and aabaab does not count because it is not strictly smaller than shift_3(aabaab).

For the questions JJ through GGG the type of problem is the same. You are given an algebraic expression and I want you to write a combinatorial description such that the number of elements in that combinatorial description is equal to the expression. You may assume that n,k are some fixed non-negative integers. C(n,k) and P(n,k) are the notations for _nC_k and _nP_k used in section 3-1 of the book.
JJ. SEQUENCES AND SETS OF OBJECTS II: second part, question (1)
KK. SEQUENCES AND SETS OF OBJECTS II: second part, question (2)
LL. SEQUENCES AND SETS OF OBJECTS II: second part, question (3)
MM. SEQUENCES AND SETS OF OBJECTS II: second part, question (4)
NN. SEQUENCES AND SETS OF OBJECTS II: second part, question (5)
OO. SEQUENCES AND SETS OF OBJECTS II: second part, question (6)
PP. SEQUENCES AND SETS OF OBJECTS II: second part, question (7)
QQ. SEQUENCES AND SETS OF OBJECTS II: second part, question (9)
RR. SEQUENCES AND SETS OF OBJECTS II: second part, question (10)
SS. SEQUENCES AND SETS OF OBJECTS II: second part, question (11)
TT. SEQUENCES AND SETS OF OBJECTS II: second part, question (12)
UU. SEQUENCES AND SETS OF OBJECTS II: second part, question (13)
VV. SEQUENCES AND SETS OF OBJECTS II: second part, question (14)
WW. SEQUENCES AND SETS OF OBJECTS II: second part, question (15)
XX. (a₁ + a₃ + a₅ + ... + a_2n-1 + a_2n+1) b_2n+1
YY. a₁ b₁ + a₃ b₃ + a₅ b₅ + ... + a_2n+1 b_2n+1
ZZ. C(a_n, 0) + C(a_n,1) + C(a_n,2) + ... + C(a_n, a_n)
AAA. C(a_n, 0) + C(a_n,2) + C(a_n, 4) + ... + C(a_n, 2 floor(a_n/2))
BBB. a_n(a_n -1) ... (a_n-k+1)
CCC. 1! a₁ + 2! a₂ + 3! a₃ + ... + n! a_n
DDD. n a_k + (n-1) a_k+1 + ... + (k+1) a_n-1 + k a_n
EEE. b_n a_k + b_n-1 a_k+1 + ... + b_k+1 a_n-1 + b_k a_n

FFF. a₁! + a₂! + ... + a_n!

*HHH. Show by a combinatorial argument (this can be explained using addition principle only) that C(n+2,3) = C(2,2) + C(3,2) + C(4,2) + ... + C(n+1,2)
III. Using the a_i= number of widgets of size i, find an expression for the number of pairs whose first element is a subset of the integers 1 through n of size 2 and a widget of size less than or equal to n but greater than or equal to the larger of the two numbers in the set.

I handed out a worksheet with exercises on November 22, 2007.
I there was a second worksheet with more problems on it on November 29, 2007. This is the worksheet titled 'SEQUENCES AND SETS OF OBJECTS II' mentioned above.

Here is what I have recorded for problems that people signed up for. I know that I have assigned and I didn't write down who is responsible for problem "J." Problems marked with an * do not have an owner (I think, please correct me if these were claimed). You may email me and claim them if you want them.

I would like to get a system which is a little more reliable for distributing problems but since I want everyone to post their solution I need 60-75 problems by the end of the term and I am not looking for just counting problems or just number theory problems, I want ones that are related to what we are doing in class and are going to challenge you to explain clearly your solution.

I mentioned in class my criterion for what I am looking for in these solutions:
(1) clear - no vague sentences that have multiple interpretations, no gaps in the explanation, very direct and to the point
(2) complete - include all relevant details. If you are writing a solution to a counting problem about cards, I want to see the connection between the description of what you are counting and how you are creating a procedure to which you can apply the addition and multiplication principle. This need only be one sentence, but if that sentence is missing the solution is not complete. For other types of problems I am looking for a logical sequence of arguments.
(3) short - this this a secondary criterion but it is extremely important that you not ramble on. I am not looking to see how you solved this problem, save that for your own notes. What I am looking for is that you explain to me why what you said is true and not a sentence more.

I need to be convinced of one thing only: beyond a shadow of a doubt, your solution is correct.

Abbasi	Nader	?	W	RR
Aniceto	Paul	C	X	SS
Bhatti	Abbas	3-1 #14	Z	TT
Constantin	Violeta	1-1 #16	I	UU
Cuda	Michael	D	L	VV
Curic	Vidak	H	T	YY
Cuschieri	Pierre	2-2 #7	GG	KK
Filizola	Regiane	1-2 #3	Y	LL
Glavine	Vincent	B	U	ZZ
Goyat	Laxmi	1-1 #10	JJ	III
Heron	Radcliffe	3-1 #3	R	MM
Lim	Louis	1-2 #4	AA	NN
Malltezi	Etleva	A	S	FFF
Nelsons	Betty-Ann	1-1 #9	BB	OO
Nwosu	Kelechi	G	V	AAA
Puzniak	Malgorzata	E	CC	BBB
Richer	Danielle	1-1 #17	Q	PP
Rieger	Margaret	B	K	WW
Roberts	Catherine	F	DD	XX
Saini	Karuna	P	GG	QQ
Soster	Mario	O	FF	CCC
Tauts	Thomas	1-1 #15	EE	DDD
Woodcock	Jennifer	2-2 #4	4-2 #3	II
Zhu	Yongliang	3-1 #13	HH	EEE

Back to the web page for Math 5020.