User jigsawmnc - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T17:55:50Z http://mathoverflow.net/feeds/user/27991 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/118522/integral-solutions-to-a-1-times-a-2-times-times-a-k-n Integral solutions to $a_1 \times a_2 \times ... \times a_k = N$ jigsawmnc 2013-01-10T11:05:48Z 2013-01-11T14:55:38Z <p>How many integral solutions are possible for the equation $a_1 \times a_2 \times \ldots \times a_k = N$ where each of $a_1, a_2, \ldots, a_k$ satisfy the property $0 \leq a_i \leq 9$?</p> <p>The question is to find out the number of possible combinations $(a_1, a_2, \dots, a_L)$ such that $(\frac{a_1}{a_2})(\frac{a_3}{a_4}) \dots = N$ with the constraint that $a_1, a_2, \dots ,a_L$ satisfy $0 \leq a_i \leq 9$. So, my approach was to consider $N$ as $\frac{N}{1}, \frac{2N}{2}, \ldots$ till $\frac{mN}{m}$ such that $mN \leq 9^k, k = L - 1 or L$. Now, if I get the possible combinations for both numerator and denominator(for all these fractions), then I could multiply and add these combination numbers to get the final result. Can any other approach be adopted for doing it?</p> http://mathoverflow.net/questions/112074/how-many-matrices-are-possible-for-the-given-arrangement/112176#112176 Answer by jigsawmnc for How many matrices are possible for the given arrangement? jigsawmnc 2012-11-12T13:56:05Z 2012-11-12T13:56:05Z <p>Perhaps <a href="http://discuss.codechef.com/questions/3706/cbars-editorial" rel="nofollow">this</a> could help.</p> http://mathoverflow.net/questions/112074/how-many-matrices-are-possible-for-the-given-arrangement How many matrices are possible for the given arrangement? jigsawmnc 2012-11-11T14:04:10Z 2012-11-12T13:56:05Z <p>Given m &amp; n, we have to find out the number of possible matrices of order m*n with the property that A(i,j) can be either 0 or 1 and that no contiguous sub-matrix of both length > 1 &amp; breadth > 1 should have same entries i.e. all of its cells shouldn't be 0 or 1. For example if m = 2 &amp; n = 2, the answer is 14: Total possibilities : 2 ^ (2 * 2); Invalid cases: when all 4 cells are 0 or 1. Therefore answer is 2 ^ (2 * 2) - 2 = 14. A sub-matrix of length > 1 &amp; breadth = 1, also breadth > 1 &amp; length = 1 is valid.</p> http://mathoverflow.net/questions/112074/how-many-matrices-are-possible-for-the-given-arrangement/112093#112093 Comment by jigsawmnc jigsawmnc 2012-11-11T20:35:27Z 2012-11-11T20:35:27Z Given that I know the value for m * m matrix. Can this value help me in finding the answer for m * (m + 1), m * (m + 2), ... matrices? http://mathoverflow.net/questions/112074/how-many-matrices-are-possible-for-the-given-arrangement/112093#112093 Comment by jigsawmnc jigsawmnc 2012-11-11T20:30:05Z 2012-11-11T20:30:05Z @Robert Israel: m's max value can be 6 and n's max value can be 2^63. Can you tell me how are you able to deduce the matrix based on m's value. Is it some algorithmic technique or just by observing it. Also, can there be derived any recursive relation? http://mathoverflow.net/questions/112074/how-many-matrices-are-possible-for-the-given-arrangement/112093#112093 Comment by jigsawmnc jigsawmnc 2012-11-11T19:41:45Z 2012-11-11T19:41:45Z How does m fit in this formula? http://mathoverflow.net/questions/112074/how-many-matrices-are-possible-for-the-given-arrangement Comment by jigsawmnc jigsawmnc 2012-11-11T19:38:36Z 2012-11-11T19:38:36Z @Pietro Majer: Contiguous means that the rows and columns of the chosen sub-matrix should be adjascent. http://mathoverflow.net/questions/112074/how-many-matrices-are-possible-for-the-given-arrangement/112083#112083 Comment by jigsawmnc jigsawmnc 2012-11-11T16:11:29Z 2012-11-11T16:11:29Z What about the case when m = 5 &amp; n = 5 and the matrix is: 0 1 0 1 0 | 0 1 0 1 0 | 0 1 0 1 0 | 0 1 0 1 0 | 0 0 1 1 0 The above is a valid case. http://mathoverflow.net/questions/112074/how-many-matrices-are-possible-for-the-given-arrangement Comment by jigsawmnc jigsawmnc 2012-11-11T15:56:45Z 2012-11-11T15:56:45Z @Per Alexandersson: It is evident that we'll have (m - 1) * (n - 1) sub-matrices of order 2 * 2. My strategy is: start picking up 2 * 2 sub-matrices starting from top-left corner i.e. containing cells A(0,0), A(0,1), A(1,0), A(1,1) of main matrix; fill it with 0 and count the total number of matrices having these cells filled in this manner. Now, I proceed on to counting those matrices where the next 2 * 2 matrix i.e. A(0,1), A(0,2), A(1,1), A(1,2) are filled with 0. However, I am not able to count the repeating cases of 2nd matrix which already appeared in the first case. How to achieve this?