Math Is Fun Forum

Aquafina

Member

Registered: 2009-05-15

Posts: 3

Pattern Problem

Hi I need help generalising the method required for question 7 in the following link:

http://www.mathpropress.com/Konhauser/Konhauser1995.html

any help will be appreciated

They have a general case in something similar,except the rows are numbered from the top going down:

http://www.cut-the-knot.org/arithmetic/NimSum.shtml

except i dont know how to prove it..

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Pattern Problem

Hi Aquafina;
 
  For # 7, Stan Wagon's problems are not easy and in addition this is an olympiad problem, they are also very hard. Have you tried googling for olympiad problems?

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Aquafina

Member

Registered: 2009-05-15

Posts: 3

Re: Pattern Problem

hi

yeah I have, but thats no help for this particular question because you can't find solutions..

the method i found on the website i quoted seemed easy to apply, any ideas how it acn be proven? I think that isn't supposed to be too hard, but I'm clueless...

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Pattern Problem

HI Aquafina;

  I'm still working on getting the number, let alone the proof.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Pattern Problem

Hi Aquafina;

To get the 666th row and the 401 column you do this: Convert 665 and 400 to binary.

Now add each binary digit according to the laws of a nim-sum. That is
1+0 =1
0+0 =0
1+1 =0
0+1 =1
You will get.

This is 777 in base 10. So the 666 th row and the 401 column contains 777.

This is the general method, just take (row-1) and (col-1) and convert to binary. Add like a nim sum and convert answer to base 10. The proof of this method is contained in Challenging Mathematical Problems with Elementary Solutions Vol 2 by Yaglom problem 129. It is very difficult and long. I don't understand it well enough to shorten it.

Last edited by bobbym (2009-05-17 21:58:29)

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

whatismath

Member

Registered: 2007-04-10

Posts: 19

Re: Pattern Problem

Hi, I did not read Yaglom's solution but I think there
shoud be a formal proof. I filled in more than 10 rows
and columns for the matrix and think I see a pattern,
which (I think) could be proved if written carefully.
1. For each

, each row and colum of
    the

    matrix formed by  the 0 to

rows
    and columns is a permutation of 0 to

.
2. The

matrix

    has the form:
   

    where every entry of

is

plus the corresponding entry of

.

To find the (401,666) entry, bobby gave the simple computation rule and here is an illustration:
a. notice both 666, 401 are less than 1024=

b. Since

, the entry is in the upper left

.
c. By observation (2) above, (401,666) entry = (401,666-512) entry + 512, i.e. (401,154) entry + 512.
   Since

, the entry is in the lower right

.
   (401,154) entry = (401-256,154) entry+256, i.e. (145,154) entry + 256.
   Now both

, the entry is in the upper right

,
   (145,154) entry = (145-128,154-128) entry, i.e. (17,26) entry
   Continue: (17,26) entry = (17-16,26-16) entry = (1, 10) entry = (1, 2) entry+8 =1+8=9.
   Hence (401,666) entry = 9+256+512=777.

Last edited by whatismath (2009-05-18 18:42:26)

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Pattern Problem

Hi whatismath;

  I wasn't careful enough to fill in 10 rows and 10 columns without making an error. Thanks for providing your method. It seems there is always another way.

Last edited by bobbym (2009-05-20 11:55:43)

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.