Report

Chapter 3 Elementary Number Theory and Methods of Proof 3.5 Direct Proof and Counterexample 5 Floor & Ceiling Floor & Ceiling • Definition – Floor • Given any real number x, the floor of x, denoted ⎣x⎦, is defined as: ⎣x⎦ = n ⇔ n ≤ x < n + 1. – Ceiling • Given any real number x, the ceiling of x, denoted ⎡x⎤, is defined as: ⎡x⎤ = n ⇔ n-1 < x ≤ n. Examples • Compute ⎣x⎦ and ⎡x⎤ for the following: – 25/4 • ⎣25/4⎦ = ⎣6+ 1/4⎦ = 6 • ⎡25/4⎤ = ⎡6+ 1/4⎤ = 7 – 0.999 • ⎣0.999⎦ = ⎣0 + 999/1000⎦ = 0 • ⎡0.999⎤ = ⎡0 + 999/1000⎤ = 1 Examples • The 1,370 soldiers at a military base a re given the opportunity to take buses into town for an evening out. Each bus holds a maximum of 40 passengers – What is the maximum number of buses the base will send if only full buses are sent? • ⎣1,370/40⎦ = ⎣34.25⎦ = 34 – How many buses will be needed if a partially full bus is allowed? • ⎡1,370/40⎤ = ⎡34.25⎤ = 35 Addition Property of Floor • Does ⎣x + y⎦ = ⎣x⎦ + ⎣y⎦? • Can you find a counterexample where the case is not true. If so, then you can prove that equality is false. – How about x = ½ and y = ½ ? • ⎣½ + ½⎦ = ⎣1⎦ = 1 • ⎣½⎦ + ⎣½⎦ = 0 + 0 = 0 • hence, the equality is false. Proving Floor Property • Prove that for all real numbers x and for all integers m, ⎣x + m⎦ = ⎣x⎦ + m – Suppose x is a particular but arbitrarily chosen real number and m is particular but arbitrarily chosen integer. – Show: ⎣x + m⎦ = ⎣x⎦ + m • • • • • Let n = ⎣x⎦, n is integer n ≤ x < n+1 n + m ≤ x + m < n + m + 1 (add m to all sides) ⎣x + m⎦ = n + m (from previous) since n = ⎣x⎦ Thus ⎣x + m⎦ = ⎣x⎦ + m • Theorem 3.5.1 Floor of n/2 • Theorem 3.5.2 Floor of n/2 – For any n, ⎣n/2⎦ = n/2 (if n even) or (n-1)/2 (if n odd) • Examples – Compute floor of n/2 for the following: • n = 5: ⎣5/2⎦ = ⎣2 ½⎦ = 2 = (5-1)/2 = 2 • n = 8: ⎣8/2⎦ = ⎣4⎦ = 4 = (8)/2 = 4 Div / Mod and Floor • There is a relationship between div and mod and the floor function. – n div d = ⎣n / d⎦ – n mod d = n – d⎣n/d⎦ • From the quotient-remainder theorem, n = dq + r and 0≤r<d a relationship can be proven between quotient and floor. • Theorem 3.5.3 – If n is any integer and d is a positive integer, and if q = ⎣n/d⎦ and r = n – d⎣n/d⎦ then, n = dq + r and 0≤r<d