Daniel Lewis
CSC165 A3
  
1)
Claim S1: for all x in R, ceil(x) = -floor(-x)
Proof:
Let x be an element of R //x arbitrary
  Let (y = floor(-x)) be an element of Z //y specific
		So y <= -x //definition of floor(-x)
		Therefore -y >= x //times -1
		And for all w in Z, w <= -x -> w <= y //definition of floor(-x)
		So for all (-w) in Z, -w >= x -> -w >= -y //times -1
		Substituting z = -w
			Then for all z in Z, z >= x -> z >= -y
		And since -y is an element of Z //Z closed under multiplication
		Therefore -y is an element of Z /\ -y >= x 
							/\ for all z in Z, z >= x -> z >= -y
		Thus -y = ceil(x) //from above
		Thus -floor(-x) = ceil(x) //substitution
Thus for all x in R, -floor(-x) = ceil(x) //x is arbitrary

2)
Claim: In the two dimensional array S[m][n], S[2][5] = 9
Proof:
Let a be an element of D intersect {8, 3, 6, 7} //#s in row 2
	Case 1: S[2][5] = a
		S[2][1] = 8 //diagram
		S[2][4] = 3 //diagram
		S[2][6] = 6 //diagram
		S[2][8] = 7 //diagram
		Since S[2][5] = S[2][1] \/ S[2][5] = S[2][4] \/ S[2][5] = S[2][6] 
					\/ S[2][5] = S[2][8] //def'n a
		Then 5 = 1 \/ 5 = 4 \/ 5 = 6 \/ 5 = 8 //R2 -><-
		So S[2][5] ~= a //assumption leads to contradiction
		So S[2][5] is not an element of D intersect {8, 3, 6, 7} //definition 
																														 //of a
Let b be an element of D intersect [1, 6] //#s in columns 4 and 6
	Case 2: S[2][5] = b
		S[1][4] = 1 //diagram
		S[2][4] = 3 //diagram
		S[3][4] = 2 //diagram
		S[1][6] = 5 //diagram
		S[2][6] = 6 //diagram
		S[3][6] = 4 //diagram
		Since ceil(1 / 3) = ceil(2 / 3) = ceil(3 / 3) = 1 //ceil(row / 3)
					/\ ceil(4 / 3) = ceil(5 / 3) = ceil(6 / 3) = 2 //ceil(column / 3)
					/\ (S[2][5] = S[1][4] \/ S[2][5] = S[2][4] \/ S[2][5] = S[3][4]
							\/ S[2][5] = S[1][6] \/ S[2][5] = S[2][6] \/ S[2][5] = S[3][6])
							//definition of b
		Then (2 = 1 /\ 5 = 4) \/ (2 = 2 /\ 4 = 5) \/ (2 = 3 /\ 5 = 4) 
					\/ (2 = 1 /\ 5 = 6) \/ (2 = 2 /\ 5 = 6) \/ (2 = 3 /\ 5 = 6) //R4 
																																			//-><-
		So S[2][5] ~= b //assumption leads to contradiction
		So S[2][5] is not a element of D intersect [1, 6] //definition of b
Therefore S[2][5] is not an element of (D intersect {8, 3, 6, 7})
																				union (D intersect [1, 6]) //cases 
																																	 //1 & 2
Then S[2][5]  is not an element of D intersect [1, 8] //union operation
But there exists k in D, S[2][5] = k //R1
So S[2][5] = D - (D intersect [1, 8]) = 9 //only element in D not ruled out