prob035: Molnar's Problem
Results
A simple way to state this problem is as a pair consisting of the order of the
matrix and an upper bound on the entries (disallowing negative entries).
For Guy's variant (see [2]), where 0 entries are also disallowed and the determinants
of the two matrices are constrained to be equal, the number of unique
solutions are as follows (as shown in [1]):
| Order, UBound |
No. Solutions |
Order, UBound |
No. Solutions |
| 3, 3 |
0 |
3, 4 |
0 |
| 3, 5 |
0 |
3, 6 |
0 |
| 3, 7 |
0 |
3, 8 |
0 |
| 3, 9 |
3 |
3, 10 |
4 |
| 3, 11 |
5 |
4, 3 |
0 |
| 4, 4 |
0 |
4, 5 |
13 |
Of course, this table can be extended indefinitely. The difficulty
of finding all solutions increases rapidly with the size of the domains.
The references page gives pointers to several
solutions, both individuals and parametric families. Some examples
include:
| 2 | 3 | 2 | |
2 | 3 | 5 | |
2 | 3 | 6 | |
5 | 7 | 6 | |
8 | 7 | 8 | |
10 | 7 | 12 | |
| 4 | 2 | 3 | , |
3 | 2 | 3 | , |
3 | 2 | 3 | , |
6 | 4 | 7 | , |
12 | 11 | 7 | , |
4 | 2 | 7 | |
| 9 | 6 | 7 | |
9 | 5 | 7 | |
17 | 11 | 16 | |
17 | 16 | 20 | |
17 | 15 | 16 | |
17 | 12 | 20 | |
- A. M. Frisch, C. Jefferson, I. Miguel,
"Constraints for Breaking More Row and Column Symmetries,"
Proceedings of the 9th International Conference on Principles and
Practice of Constraint Programming, 2003.
- R. K. Guy, "Unsolved Problems in Number Theory", Section F28,
Sringer-Verlag, 1994.
Back to CSPLib home page.