Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 (Tek) 9/26/83; site tekchips.UUCP
Path: utzoo!watmath!clyde!burl!hou3c!hocda!houxm!vax135!cornell!uw-beaver!tektronix!tekchips!stevev
From: stevev@tekchips.UUCP (Steve Vegdahl)
Newsgroups: net.math
Subject: Re: Trivial Proof Needed
Message-ID: <47@tekchips.UUCP>
Date: Fri, 31-Aug-84 14:49:18 EDT
Article-I.D.: tekchips.47
Posted: Fri Aug 31 14:49:18 1984
Date-Received: Mon, 3-Sep-84 08:14:43 EDT
Organization: Tektronix, Beaverton OR
Lines: 25

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
				********************************