[thakarsagar]

Originally Posted by clsuresh

Quote:
Originally Posted by clsuresh
SAGAR,

I think this will not work out for the squares of dimension 2 x 2 on a chess board.

Sagar,
Applying this to chess board (8 x and for sqares of side 2 x 2
ceil(m/p) * [ceil(n/p) - 1] + ceil(n/p) * [ceil(m/p) - 1]....
we get it as
4*(4-1) + 4*(4-1) = 24
But the answer is > 24.
regards,
Suresh.

hi suresh,
i observed an interesting thing...
for a 2*2 small square and large square of size n the no of adjacent sides "only on one side of the sqaure" is as follows...
Size: no of sides adjacent.
4:1
5:2
6:3
7:4
8:5
9:6
10:7
....and so on....
For 3*3 small squares, the no of adjacent sides is as follows...(Only on one side of the sqaure)
Size: no of sides adjacent.
6->1
7->2
8->3
9->4
so do you think this will work for square 2*2 -> ceil(m/p) *(n-3) + ceil(n/p)*(m-3) (where p = 2)?????
The idea is to traverse on the rows as the no of times given by ceil(m/p) and n-3 is generalized from the above observation...
Similarly, for a 3*3 -> ceil(m/p) * (n-5) + ceil(n/p) * (m-5)...
????
Please verify the ceil(n/p) in all cases...i am skeptical about it....
-sagar

ps: i think instead of ceiling it should be floor....

[clsuresh]

Fine Sagar,

I think this would be simple. Try to follow my approach because it would be more clear if I can draw a chess board.

Firstly, on 8 x 8 board there r 9 horizontal lines and nine vertical lines.





Now Let me discuss about sqares of side 1 x 1. Since i need two squares of having a side commom which means that i should have a line in common. So instead searching for squares let me think about the lines here.

It is clear that the 1st horizontal line and 9th horizontal line as well as 1st vertical line and 9 th vertical line cannot be the lines that can form the common side.

So out these 18 lines now I am left with 14 lines.
Now consider the 2nd horizontal line.
From this I can select two squares that share this line in 8 ways.
This is going to be the same when I consider the 2 vertical line as well as all the remaining lines.

So total no. of ways is 14 x 8 = 112.

Now let's come to the squares of 2 x 2 .
It is clear that the first two and last two horizontal lines as well as first two and last two veritcal lines cannot be the common sides of the two squares we select.
So we are left with 10 lines now. [18- (4 horiz+4 vert)]
Now considering the above 10 lines from each line I can select two 2 x 2 squares in 7 ways.
So total no. of ways will be 10 x 7 = 70

Now if I talk about m x m dimensional board
First the no. of lines on the board is 2m+2 ( i.e m+1 horiz, m+1 vert)
Now the no. of line that can contribute the common side is
(2m+2-4s) where s is the dimension the square.

With each line total no. of chances is (m-s+1).
So total no. of ways will be
(2m+2-4s) x (m-s+1).
This will holds good not only to m x m but also any m x n rectangular board.
I hope I am clear and I have spent last night regarding this problem and counted them manually on a 20 x 18 board and I got it right. I think the above method is lucid. SAGAR,If U need any further information pls give me ur contact no. to my personal mail.

Regards,
Suresh

[clsuresh]

Guys,

I will give u the generalisation for m x n dimensional board also provided only if u try on the same lines which i discussed above for atleast tonight. Tommorrow I will catch up with u and i hope that i will get an answer tommorrow.

Byeeeeee
Suresh

[thakarsagar]

Originally Posted by clsuresh

sagar,

Is it 229. confirm.........

Suresh, answer is 242...i too am getting it through brute force...
we need to find the no of solutions to the equations ,
a+ 5b + 10c + 25d = 100

i) d = 0
Total solutions = 21 + 19 + ... + 1 = 121
ii) d = 1
Total solutions = 16 + 14 + .. + 2 = 72
iii) d = 2
Total solutions = 11 + 9 + ... + 1 = 36
iv) d = 3
Total solutions = 6 + 4 + 2 = 12
v) d = 4
Total solutions = 1
Add them ....=> 242 ....
regards,
-sagar

Explanation: At any time, values of a , b ,c and d are in the following range...
b-> 0-20
c-> 0-10
d-> 0-4
so counting becomes simpler...

[clsuresh]

Sagar,

Yes it is 242. I have done a mistake in adding them. The way in which I have done is almost same.

Just a little bit of it.

a+5b+10c+25d=100

First of all a=0, 5,10,15,...................,100.

The corresponding values that 5b+10c+25d can take will be 100, 95,90,........,0

i.e b+2c+5d =20,19,18,17,............,0

Now verifying the values that satisfy this I got it as 242.

Regards,
Suresh.

[khanna_sumit]

Originally Posted by thakarsagar

Suresh, answer is 242...i too am getting it through brute force...
we need to find the no of solutions to the equations ,
a+ 5b + 10c + 25d = 100

i) d = 0
Total solutions = 21 + 19 + ... + 1 = 121
ii) d = 1
Total solutions = 16 + 14 + .. + 2 = 72
iii) d = 2
Total solutions = 11 + 9 + ... + 1 = 36
iv) d = 3
Total solutions = 6 + 4 + 2 = 12
v) d = 4
Total solutions = 1
Add them ....=> 242 ....
regards,
-sagar

Explanation: At any time, values of a , b ,c and d are in the following range...
b-> 0-20
c-> 0-10
d-> 0-4
so counting becomes simpler...

i dont know what u want to say that conting become easier...as far as answer is concernd it is absolutely correct....but i got the solution using the method for finding the solutions of diophantine equations.....

here is my method

a+5b+10c+25d=100
i'll xplaine it for one value of d=0 and same process can be used for other values of d....
d=0 or a+5b+10c = 100 or a+5b = 100-10c
for solving such equations we can first find a solution to a+5b=1 which in this case can be found very easily because the coefficients i.e. 1 and 5 are easier to deal with .....for difficult looking coeffs. we can use the simple continued fractions....for this case a=-4 and b=1 satisfies the equation a+5b=1.....
therefore a solution to the equation a+5b=100-10c will be
a=-4(100-10c) and b=1(100-10c) which can be understood with a little reasoning..if a solution to equation type ax+by=c is known (lets say x=A,y=B satisfies it) then whole series of solutions is given by (A+bt) and (B-at) for any positive or negative integral value of t.....therefore in this case the general solution is given by a=-400+40c+5t and b=100-10c-t.....since a>=0 and b>=0,
putting the values of a and b we get 80-8c<=t<=100-10c for all integral t's satisfying this conditionwe will get different solutions for the basic equation....also 0<=c<=10 that makes the series 21+19+17.......
i hope this helps to find a definitive solution...

rgds
SUMIT

[thakarsagar]

Originally Posted by khanna_sumit

i dont know what u want to say that conting become easier...as far as answer is concernd it is absolutely correct....but i got the solution using the method for finding the solutions of diophantine equations.....

here is my method

a+5b+10c+25d=100
i'll xplaine it for one value of d=0 and same process can be used for other values of d....
d=0 or a+5b+10c = 100 or a+5b = 100-10c
for solving such equations we can first find a solution to a+5b=1 which in this case can be found very easily because the coefficients i.e. 1 and 5 are easier to deal with .....for difficult looking coeffs. we can use the simple continued fractions....for this case a=-4 and b=1 satisfies the equation a+5b=1.....
therefore a solution to the equation a+5b=100-10c will be
a=-4(100-10c) and b=1(100-10c) which can be understood with a little reasoning..if a solution to equation type ax+by=c is known (lets say x=A,y=B satisfies it) then whole series of solutions is given by (A+bt) and (B-at) for any positive or negative integral value of t.....therefore in this case the general solution is given by a=-400+40c+5t and b=100-10c-t.....since a>=0 and b>=0,
putting the values of a and b we get 80-8c<=t<=100-10c for all integral t's satisfying this conditionwe will get different solutions for the basic equation....also 0<=c<=10 that makes the series 21+19+17.......
i hope this helps to find a definitive solution...

rgds
SUMIT

hello sumit,
this is how i did....
1) when d=1
hence, we need to find no of solutions of a + 5b + 10c = 100
(a) when c = 0
a + 5b = 100
b goes from 0 to 100/5=20 => solutions = 21...
(b) when c = 1
a + 5b = 90
b goes from 0 to 18 => solutions = 19....
Now, don't calculate fully....it will follow the sequence 21 + 19 + ... + 1
2) when d = 2
hence, we need to find a + 5b + 10c = 75
(a) c = 0 , b goes from 0 to 75/5=15 => 16 solutions...
(b) c = 1 , b goes from 0 to 65/5 = 13 => 14 solutions....
And so no => 16 + 14 + ... + 2
And so on for the other cases...
-sagar

[thakarsagar]

Suresh and sumit,

Do you see a general method of finding the total no of possible solutions to any given equation a + by +cz = d??? (a , b c and d been integers...)

regards,
-sagar

ps: Apart from summit's method...

[khanna_sumit]

Originally Posted by thakarsagar

hello sumit,
this is how i did....
1) when d=1
hence, we need to find no of solutions of a + 5b + 10c = 100
(a) when c = 0
a + 5b = 100
b goes from 0 to 100/5=20 => solutions = 21...
(b) when c = 1
a + 5b = 90
b goes from 0 to 18 => solutions = 19....
Now, don't calculate fully....it will follow the sequence 21 + 19 + ... + 1
2) when d = 2
hence, we need to find a + 5b + 10c = 75
(a) c = 0 , b goes from 0 to 75/5=15 => 16 solutions...
(b) c = 1 , b goes from 0 to 65/5 = 13 => 14 solutions....
And so no => 16 + 14 + ... + 2
And so on for the other cases...
-sagar

fine. i got it......practise the method i have given....it is very effective method...
rgds
Sumit

[khanna_sumit]

Originally Posted by thakarsagar

Suresh and sumit,

Do you see a general method of finding the total no of possible solutions to any given equation a + by +cz = d??? (a , b c and d been integers...)

regards,
-sagar

that method is the general solution for the diophantine equation ax+by+cz=d.....