wu :: forums - Print Page


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

        riddles >> medium >> coin placing
        
(Message started by: cool_joh on Dec 17^th, 2008, 5:20pm)

Title: coin placing
Post by cool_joh on Dec 17^th, 2008, 5:20pm

We have 111 coins. They are to be placed in unit cells of the table nhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/times.gifn so that the number of coins in any two neighboring (i.e. sharing a common side) cells differs exactly by 1 (a cell may contain several coins and may be empty, too). For which maximal n is this possible?

Title: Re: coin placing
Post by aicoped on Dec 17^th, 2008, 9:30pm

The answer is odd. It has no solutions for an even number square.

And trivially it can be done for a 1x1 square.

It can be done for 3x3 with 13 on the 4 corners and 12 on the four "sides" with 11 in the middle.

Five by five can be done. Imagine a checkerboard with all of the 13 squares that would be the same color as the center square equal to 5. And the rest are equal to 4. That answer will be too high by 2, so any corner instead of being 5 will be 3.

If I had to guess, I would suggest the answer is 13.

This is because for 15 square, it has 225 squares in it. And at least half of them must contain a 1, which would be 112, so 15 is impossible. And thirteen is theoretically possible, so It should not be to hard to actually fine the zeros ones and 2's that would make it work.

Title: Re: coin placing
Post by towr on Dec 18^th, 2008, 1:42am

on 12/17/08 at 21:30:18, aicoped wrote:

If I had to guess, I would suggest the answer is 13.

This is because for 15 square, it has 225 squares in it. And at least half of them must contain a 1, which would be 112, so 15 is impossible. And thirteen is theoretically possible, so It should not be to hard to actually fine the zeros ones and 2's that would make it work.

Just start off with a checkerboard of zeroes and ones, (with ones in the corners), then replace an arbitrary 13 zeroes with twos.
(13²+1)/2+2*13=111
Each zero and two is surrounded by ones, each one is surrounded by twos or zeroes.

You can find solutions for each smaller odd square in a similar way.
And for even numbers of coins there are solutions for both odd and even squares.

Title: Re: coin placing
Post by aicoped on Dec 18^th, 2008, 4:35am

I realized that while lying in bed and hoped to post here before someone pointed thta out.

Title: Re: coin placing
Post by towr on Dec 18^th, 2008, 4:48am

Hah; you snooze, you lose ;D

Title: Re: coin placing
Post by cool_joh on Dec 18^th, 2008, 5:28am

LOL ;D You're correct, the answer is 13.

This problem is taken from Zhautykov Olympiad, an international mathematics olympiad held annually in Kazakhstan.