Graph Theory - # of lines and combinations?

Badges: 2
Report Thread starter 3 weeks ago
Hello All,

See picture below:
Name:  1000.png
Views: 7
Size:  6.9 KB
There exist an infinite plane with infinite number of dots. For sake of argument, let's assume they are 1 inch away from each other.
Name:  1001.png
Views: 7
Size:  53.2 KB
However, below(on your far left) you can see 3 lines already made. The last line is the yellow one.
What you see on your right, are all combinations of possible moves. Move is defined as structure of lines until you reach an empty dot.
Thus, there are 6 combinations of single line(on top). While on bottom you see 10 combinations. 5 of them moves with 2 lines, and 5 with 3 lines.
Total # of combinations is 16.
So far so good?
Well the basic unsolved questions are:
* Does formula exist to calculate total number of combinations(16 in this case) just by looking at the initial graph of 3 lines?
** Does formula exist to show the breakdown of all combinations (6 for single line, 5 for 2 lines, 5 for 3 lines?
*** is 16 the biggest number of combinations that you can make from 3 line starting configuration? For instance: Try to calculate # of combinations (1 lines, 2 lines, 3 lines) from this initial variation:
Name:  1002.png
Views: 11
Size:  3.8 KB

To not spoil the fun, i will just say there is more than 16. So is this the best solution? How we can prove that this is the best we can do? Obviously we can prove that just by doing all 3 line configurations by hand, but what if we take it to next level? What's the best 4 line configuration and how many combinations it has? How about 5,6.7...(n) ? The tree expands quite rapidly, and also few things need to be explained:

Combinations vs Permutations:

Name:  1003.png
Views: 10
Size:  4.1 KB
Above, there are 4 lines as starting configuration. In this case, there are 36 combinations OR 41 permutations. The reason is because you can go from A > B > C > D or C > B > A > D. Once again, is the a formula to calculate combinations (36) and Permutation(41) from any starting configuration?

Name:  1004.png
Views: 16
Size:  6.5 KB
Notation + Final info to consider:
Name:  1005.png
Views: 9
Size:  29.0 KB

Using above notation, you can notice that each configuration is unique and might have different #s of combinations and or permutations. For example:

Name:  1006.png
Views: 8
Size:  18.3 KB

Anyone with any input, either mechanical or potentially writing a code to get the answers How many combinations/Permutations for each variation with up to 10 lines as a starting configuation, would be greatly appreciated. If your program can handle bigger starting configurations, that's even better!

Thank You and enjoy!
Last edited by Laubarr; 3 weeks ago
Badges: 18
Report 3 weeks ago
Could you explain where the question comes from? You've posted it in other places as well.
Badges: 2
Report Thread starter 3 weeks ago
(Original post by mqb2766)
Could you explain where the question comes from? You've posted it in other places as well.

It comes from paper-soccer/pencil soccer (there are many names).

The game is pretty simple to play, however i'm interested more in the mathematical aspect. What i asked in main thread is in general terms of the problem.
Also, there is no program/bot in the game that could play even at 1600 ELO, let alone 2700-2800+.
Obviously there AI's, however these are simple programs that are just constantly attacking the goal.

To recap, my main goal is to find a formula to count combinations/permutations of each line variation. Once formula is known, then this can be extrapolated into over 300 lines that you can do in the whole game, before you have to hit one of the goals to score a goal. The upper bound of permutations should not be more than 8^310.

Yes, i posted it on few forums already in order to get different ideas how to approach it, or if it is even possible to find formula, but without success so far. The problem seems to be either too hard for current graph theory to solve, or my explanation of the problem might be chaotic and not well explained (although i try to make it as short as possible)

Let me know if any questions.

Thank You!
Attached files

Quick Reply

Attached files
Write a reply...
new posts
to top
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.


Current uni students - are you thinking of dropping out of university?

Yes, I'm seriously considering dropping out (57)
I'm not sure (14)
No, I'm going to stick it out for now (132)
I have already dropped out (6)
I'm not a current university student (180)

Watched Threads

View All