ams@hou4b.UUCP (08/31/84)
I need a proof of the following trivial assertion: Let (- denote "is a member of" Let |R denote the set of real numbers Let |N denote the set of natural numbers Let there be two numbers n and x, n (- |N and x (- |R. Then let n be the greatest number such that n <= x. We can denote functions that give the largest integer n <= x: n = int (x) = |_ x _| <= x Now let R (x) denote the rounding function: n = R (x) = |_ x + 1/2 _|, where n (- |N and x (- |R. Assertion: I maintain that: | a + |_ b / 2 _| | R (a / b) = | --------------- |; a,b (- |N, b != 0. |___ b ___| For the case where b is even this is trivial, since int (b/2) = b/2 and int ((a + b/2)/b) = (a/b + 1/2) = R (a/b). However, I don't seem to have a satisfactory proof for the case where b is odd. Any leads would be appreciated: I am sure the problem is really trivial and I am not looking at it in the right way. Andrew Shaw AT&TISL 834-4085 HO 1C-412A houx[a-z]!hou4b!ams
stevev@tekchips.UUCP (Steve Vegdahl) (08/31/84)
Problem: Show that Round(a/b) = Floor((a+Floor(b/2))/b), a, b integers, b non-zero 1. Because whole numbers can be factored out, it can be assumed that 0 <= a < b without loss of generality. 2. As the proposer pointed out, the problem is trivial for b even; we therefore rewrite b as 2k+1, k >= 0
stevev@tekchips.UUCP (Steve Vegdahl) (08/31/84)
Problem:
Show that Round(a/b) = Floor((a+Floor(b/2))/b),
a, b integers, a >= 0, b > 0
1. Because whole numbers can be factored out, it can be assumed that
0 <= a < b without loss of generality.
2. As the proposer pointed out, the problem is trivial for b even; we
will therefore rewrite b as 2k+1, k >= 0. Thus, 0 <= a <= 2k.
3. This results in the problem being that of showing that
Floor(1/2 + a/(2k+1)) = Floor(1/2 + a/(2k+1) - 1/(4k+2))
for all k >= 0, 0 <= a <= 2k.
4. By plugging in values both sides <= 0 if a <= k, and both sides are
>= 1 if a > k.
5. Clearly, neither side can be anything but 0 or 1; therefore the
expressions are always equal, given the restrictions.
Note that by step 1, the result still hold if *a* is negative; if *b* is
negative, however, the equality fails (e.g., (a,b) = (0,-1)).
********************************
Steve Vegdahl NOT RESPONSIBLE FOR
Computer Research Lab. typos
Tektronix, Inc. logical errors
Beaverton, Oregon actions of my pet alligator
********************************