Competition on difficult problems for programmers
Hello, harabrachitel.
Recently, I like to hold contests for programmers-mathematicians, but these contests differ somewhat from programming contests, at least in that I offer tasks that do not have an effective algorithm for solving. In addition, the proposed tasks that either no one had ever solved, or solved very little, but did not achieve serious success. The last feature of these tasks is that they are somehow connected with enumerative combinatorics, that area of ​​mathematics that was buried in Russia together with other useful areas of science “you know when”. But this is less important.
')
An example of such a competition is the competition for the task of placing 6 queens on an n × n chessboard. For the first time, it was solved precisely within the framework of my competition (an explicit formula was obtained for the number of all configurations) and caused a resonance among those researchers engaged in enumeration combinatorial problems. The formula itself allowed the researchers of this task to build new and stronger hypotheses. In more detail the position in relation to such tasks I expressed on Habré in this article .
Another contest related to the physics of polymers in the future will allow researchers in this field to show that lattices with defects are also quite amenable to calculation, like lattices without defects that are practically unreal in the real world. This was illustrated by the example of calculating “pre-Hamiltonian” cycles. The corresponding competition was supported by the article about the dynamic programming method . The algorithm described in this article (with appropriate implementation) is by far the fastest in the world (modestly, but it is). With more serious computing power, one could talk about obtaining significant results in enumerative combinatorics ... but dreaming is not harmful. In short, this competition also proved to be useful for science.
Now I hold one competition “just like that”, even without a prize fund, and I propose to solve not the most difficult tasks from my repertoire. What for? Just so that amateurs can compete (of course, if they have free time), they could fight with other amateurs alike. The proposed tasks are difficult (in any case, the existence of an effective algorithm for solving them has not been proved), so you will have to fight not in the classical sense (as in the programming contest - for speed and quality), but in the sense of "who has a better approach." And someone may have more power at hand, also welcome. In any case, I personally am not interested in who will win, but in the result obtained by common forces in the process of competition. Practice has shown that the last two of my competitions were practically useful for science.
The contest itself will be held on my blog, where, in addition to other contests, posts have been published with a completely different meaning from programming. You can simply ignore them, and immediately select the “ Contests ” section in the menu. The fact is that I cannot yet create a separate resource for contests for personal reasons and for reasons of insufficient experience in their conduct, so for now they will train by conducting them on a blog.
A detailed description of the tasks is provided on the contest pages, here I briefly outline the conditions.
Given a natural number n. Find a minimal positive integer k such that the number 3 k contains at least n consecutive zeros in the decimal notation. For example, for n = 1, the answer is k = 10, since 3 10 = 59 0 49 and this is the first of the powers of the three that contains one zero. For n = 2, the answer is k = 35, since 3 35 = 5 00 31545098999707 and this is the first of the powers of the three containing two zeros.
There is a well-known problem of dominoes (reference to English), or the problem of dimers. The meaning of the task is to count the number of ways to pitch a chessboard of size m Ă— n with dominoes of size 1 Ă— 2, and so that the dominoes do not overlap, do not crawl over the edges of the board and completely cover the board. For example, if n = m = 2, then there are only two ways (both dominoes vertically or both horizontally).
Now let's "turn" our board into a cylinder, connecting the left and right borders. In this case, any coating can be represented as follows: if the domino gets out of the left edge, then its second half appears on the right, and vice versa. It is required to count the number of tilings of such a square chess cylinder of 2n Ă— 2n size. For n = 1, the answer will be 5, and for n = 2, the answer is 121 ... If it is not very clear, there are pictures on the contest page.
A square grid of size n Ă— n is given. It can detect simple cycles of length 4, 6, 8, etc., up to the longest possible length. [A simple loop is a loop that has no self-intersections]. For example, on a 2 Ă— 2 grid, there is one cycle with a length of 4. On a 3 Ă— 3 grid, there are 4 cycles with a length of 4, 4 cycles with a length of 6 and 5 cycles with a length of 8, that is, the answer is a sequence [4,4,5]. On the 4 Ă— 4 grid, the answer will be the sequence [9,12,26,52,76,32,6] (lengths from 4 to 16). It is required to name the answers for n = 5,6, ...
So welcome to all participants. Those who do not understand the meaning of my contests and detractors, please do not show anything. Good luck!
Ps. Yes, it would be appropriate to publish in the blog "I am promoting", but I do not have enough karma for this. This post is also related to “Sport Programming”.
Recently, I like to hold contests for programmers-mathematicians, but these contests differ somewhat from programming contests, at least in that I offer tasks that do not have an effective algorithm for solving. In addition, the proposed tasks that either no one had ever solved, or solved very little, but did not achieve serious success. The last feature of these tasks is that they are somehow connected with enumerative combinatorics, that area of ​​mathematics that was buried in Russia together with other useful areas of science “you know when”. But this is less important.
')
An example of such a competition is the competition for the task of placing 6 queens on an n × n chessboard. For the first time, it was solved precisely within the framework of my competition (an explicit formula was obtained for the number of all configurations) and caused a resonance among those researchers engaged in enumeration combinatorial problems. The formula itself allowed the researchers of this task to build new and stronger hypotheses. In more detail the position in relation to such tasks I expressed on Habré in this article .
Another contest related to the physics of polymers in the future will allow researchers in this field to show that lattices with defects are also quite amenable to calculation, like lattices without defects that are practically unreal in the real world. This was illustrated by the example of calculating “pre-Hamiltonian” cycles. The corresponding competition was supported by the article about the dynamic programming method . The algorithm described in this article (with appropriate implementation) is by far the fastest in the world (modestly, but it is). With more serious computing power, one could talk about obtaining significant results in enumerative combinatorics ... but dreaming is not harmful. In short, this competition also proved to be useful for science.
Now I hold one competition “just like that”, even without a prize fund, and I propose to solve not the most difficult tasks from my repertoire. What for? Just so that amateurs can compete (of course, if they have free time), they could fight with other amateurs alike. The proposed tasks are difficult (in any case, the existence of an effective algorithm for solving them has not been proved), so you will have to fight not in the classical sense (as in the programming contest - for speed and quality), but in the sense of "who has a better approach." And someone may have more power at hand, also welcome. In any case, I personally am not interested in who will win, but in the result obtained by common forces in the process of competition. Practice has shown that the last two of my competitions were practically useful for science.
Tasks
The contest itself will be held on my blog, where, in addition to other contests, posts have been published with a completely different meaning from programming. You can simply ignore them, and immediately select the “ Contests ” section in the menu. The fact is that I cannot yet create a separate resource for contests for personal reasons and for reasons of insufficient experience in their conduct, so for now they will train by conducting them on a blog.
A detailed description of the tasks is provided on the contest pages, here I briefly outline the conditions.
Problem 1. Three in degree n
Given a natural number n. Find a minimal positive integer k such that the number 3 k contains at least n consecutive zeros in the decimal notation. For example, for n = 1, the answer is k = 10, since 3 10 = 59 0 49 and this is the first of the powers of the three that contains one zero. For n = 2, the answer is k = 35, since 3 35 = 5 00 31545098999707 and this is the first of the powers of the three containing two zeros.
Task 2. Dimers on the cylinder
There is a well-known problem of dominoes (reference to English), or the problem of dimers. The meaning of the task is to count the number of ways to pitch a chessboard of size m Ă— n with dominoes of size 1 Ă— 2, and so that the dominoes do not overlap, do not crawl over the edges of the board and completely cover the board. For example, if n = m = 2, then there are only two ways (both dominoes vertically or both horizontally).
Now let's "turn" our board into a cylinder, connecting the left and right borders. In this case, any coating can be represented as follows: if the domino gets out of the left edge, then its second half appears on the right, and vice versa. It is required to count the number of tilings of such a square chess cylinder of 2n Ă— 2n size. For n = 1, the answer will be 5, and for n = 2, the answer is 121 ... If it is not very clear, there are pictures on the contest page.
Problem 3. Cycle statistics on a square lattice
A square grid of size n Ă— n is given. It can detect simple cycles of length 4, 6, 8, etc., up to the longest possible length. [A simple loop is a loop that has no self-intersections]. For example, on a 2 Ă— 2 grid, there is one cycle with a length of 4. On a 3 Ă— 3 grid, there are 4 cycles with a length of 4, 4 cycles with a length of 6 and 5 cycles with a length of 8, that is, the answer is a sequence [4,4,5]. On the 4 Ă— 4 grid, the answer will be the sequence [9,12,26,52,76,32,6] (lengths from 4 to 16). It is required to name the answers for n = 5,6, ...
So welcome to all participants. Those who do not understand the meaning of my contests and detractors, please do not show anything. Good luck!
Ps. Yes, it would be appropriate to publish in the blog "I am promoting", but I do not have enough karma for this. This post is also related to “Sport Programming”.
Source: https://habr.com/ru/post/108550/
All Articles