wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> (A)symmetrical Sums
        
(Message started by: Sir Col on Dec 29^th, 2004, 4:49pm)

Title: (A)symmetrical Sums
Post by Sir Col on Dec 29^th, 2004, 4:49pm

Given that x,y,k [in] [bbz], find the number of solutions to each of the inequalities.

[easy]
(1) x+y [le] k, where x,y [ge] 0.

(2) |x|+|y| [le] k.

[harder]
(3) x+y [le] k, where 0 [le] x [le] y.

(4) |x|+|y| [le] k, where x [le] y.

Note: |x| is the absolute, or unsigned, value of x.

Title: Re: (A)symmetrical Sums
Post by John_Gaughan on Dec 29^th, 2004, 6:38pm

::
[hide]1. n = k + 1
[forall] x, 0 <= x <= k, [exists] y [therefore] x + y = k
There are k + 1 such x's.

2. n = 4(k + 1)
Same as 1, except that for each value of x there are four possibilities: positive and negative x and y.[/hide]
::

Title: Re: (A)symmetrical Sums
Post by towr on Dec 30^th, 2004, 1:23am

close but no cigar
'[le]' [ne] '=' ;D

Title: Re: (A)symmetrical Sums
Post by John_Gaughan on Dec 30^th, 2004, 6:15am

Ah crap, you're right. I guess this should work then:
::[hide]
1.
n = [sum]_a=0^ka+1
n = ((0+1) + (1+1) + (2+1) + ... + (k+1))
n = ((0+1+2+3+...+k) + (1+1+1+1+...+1))
n = k(k+1)/2 + (k+1)

2.
n = 4(k(k+1)/2 + (k+1))
[/hide]::

Title: Re: (A)symmetrical Sums
Post by towr on Dec 30^th, 2004, 7:23am

I'm sceptical about the second. You shouldn't count the points for (0,y) and (x,0) 4 times, nor (0,0) even twice.

You can easily draw it for small k in the integer-plane. The first is a triangle, the second two overlaid squares.
::[hide]
1) 1/2 (k+1)(k+2)
2) (k+1)² + k²
[/hide]::

:P

Title: Re: (A)symmetrical Sums
Post by towr on Dec 30^th, 2004, 7:42am

::[hide]
3)
(k+2)²/4 for even(k)
(k+1)(k+3)/4 for odd(k)

4)
[(k+2)² + k²]/2 - 1 for even(k)
(k+1)² - 1 for odd(k)
[/hide]::

Title: Re: (A)symmetrical Sums
Post by Sir Col on Dec 30^th, 2004, 9:09am

You're good, towr! I liked your explanation about the two overlapping squares for (2).

In fact, it is possible to obtain a compact single function, in terms of k, for each of (3) and (4), by making use of the integer part function.

I'm intrigued to know your approach for (3) and (4). When I was playing with these puzzle ideas it was (4) that I started with and after taking an algebraic approach I made the geometrical connection with the graph |x|+|y|[le]k (shaded square region). For efficiency in approach I used a geometrical approach with them all. For (4) I had two overlapping rectangular regions: only counting values below or on the line y=x.

Title: Re: (A)symmetrical Sums
Post by towr on Dec 30^th, 2004, 10:34am

For 3) and 4) I did the same as for 1) and 2), I drew the case k=4 and k=5
It's easy to generalize from there.

for the odd case of 4) it took me a while to recognize it was twice two overlaid squares (with sides (k+1)/2), minus of course the origin (which would otherwise be counted twice)