A problem in combinatorics

[Duhoc]

Imagine we take a sheet of paper and along the bottom lay out ten equal spaces by marking off 11 equally placed points. We label this row 1. Directly above these points we mark off another 11 points to correspond to our first eleven points only this time we divide the ten spaces of this row into ten more spaces each 1/10 the size of the interval. Now we shall say that whenever a point exists above another point, these two points “coincide.” Yes, one is above the other, but this array is only to visualize what we are asking, understanding that all these points can exist on the same line. So, so far, in the array we have constructed we have one row with 10 spaces and 11 points and a second row with 100 spaces and 101 points and 11 coincisions. Next we construct row 3, above row 2, which will complete our description of the problem. Row 3 will have 11 dots to correspond to row 1, it will have nine dots between them to correspond to the intervals between the eleven dots we arrayed in row two and 9 more dots between each of the smaller intervals of row two for a total of 1000 spaces, 1001 dots and 112 coincisions. We reach the condition of 112 coincisions because the first dot of row 3 will coincide with the first dot of row 2 and the first dot of row 1. Eleven dots of row 3 will coincide with 11 dots of row 2 and 11 dots of row 1 and additionally, nine dots of row 3 will coincide with 9 dots of row 2 one time for each of the original ten intervals for 90 coincisions, bringing the total number of coincisions to 112. Each row we add will resolve the line into intervals one order of magnitude smaller than the line beneath it
Question 1. Is there an expression to determine the number of coincisions as we have described dependent on the number of rows.
Question 2. Is there an expression to determine the number of coincisions if we were to expand our array to three dimensions.

 

[QuantumQuest]

Hi Duhoc

If this is a homework question please post it in the Homework section using the homework template.

In any case it would be helpful to create some sketch even on some smaller scale because I find it somewhat hard to follow. This would be also helpful for you in order to tackle the problem. Also, what have you come up with so far regarding the questions?

 

[Duhoc]

I have a diagram but I don't know how to post it. Okay look below. Row 1 has the original ten spaces i referred to. The first column in this diagram has 2 dots one from row 1 and 1 from row two. That represents one coincision. Row 2 will have the dots all the way across dividing each of the original 10 spaces of row 1 into ten spaces. Row 3 will have dots all the way across but each of the ten spaces of row two will be divided into ten spaces. I believe that the number of coincisions for column 1 will n(n-1)/2 where n is the number of rows. Here I am just defining what I mean by a coincision. Row 3, 4, 5, etc are resolving the spaces of the row below into ten spaces. If you need further clarification I will provide it. I think the coincisions will rise exponentially and very quickly in a three dimensional grid. Thank you for replying.
row 2 . . . . . . . . . . . .
row 1 . . . . . . . . . . .

 

[QuantumQuest]

I have a diagram but I don't know how to post it.

If it is an image (e.g. jpg, png) use the "upload" button which is at the bottom right in your post area. If you have uploaded it on some website (e.g. an image sharing website) use the "image" button (12th button from left on the top of the posting area). I don't think that the two rows you posted is of help in order to realize the description you give.

Now, if I understand it right, you're dividing each interval in each subsequent row - i.e. from second row on, in 10 sub-intervals (relatively to the length of each interval of the previous row) using 11 points every time. So, regarding the first question, how many coincident points are each time added? Can you come up with a way to relate it to the number of lines added so far? What else must be taken into account each time in order to find the total number of coincident points?

 

[Duhoc]

Call the Array of nodes (points) A. A has dimension n rows by m columns, where m depends on n. The following explains the concept for n=3; The first row of A has nodes A(1,1) ... A(1,11) The second row of A can be labeled A(2,1) . . . A(2,101). The third row can be labeled A(3,1) ... A(3,1001). Now we say the coincident points can be visualized by realizing that A(1,1), A(2,1) and A(3,1) are coincident when taken two at a time. Therefore there are 3 coincident points(3C2). The column containing A(1,2), A(2,11) and A(3,101) also have three coincident points, llikewise A(1,3), A(2,21), A(3,201) also form a column with three coincident points ... the final column is A(1,11), A(2,101), A(3,1001) of which there are three more coincident points.

If we consider the second row also forming a column, A(2,2), A(3,11) with one coincident point (coincisions). Also forming a column A(2,3), A(3,21), etc. Note this matrix has a growing number of elements for each row.

 

[Duhoc]

The above description was composed by my friend who is a Phd in math. He said it might be easier to understand for a mathematician. We disagreed on the meaning of "coincision" which I outlined in the original problem but I yielded to him. It is an extremely difficult problem but I am hoping it piques someone's interest. Thanks to all.

 

[mfb]

For every point in row 2 there is a point in row 1 => 11 matches simply because row 1 has 11 points.

For every point in row 3 there is a point in row 2 => 101 matches simply because row 2 has 101 points.
For every point in row 3 there is a point in row 1 => 11 additional matches simply because row 1 has 11 points.

For every point in row 4 there is a point in row 3 => 1001 matches simply because row 3 has 1001 points.
For every point in row 4 there is a point in row 2 => 101 additional matches simply because row 2 has 101 points.
For every point in row 4 there is a point in row 1 => 11 additional matches simply because row 1 has 11 points.
...

For every point in row n there are 11+101+...+10^n-1+1 matches because the previous n-1 rows have so many matches. It is not difficult to find an explicit expression for this sum. It is also not difficult to find an explicit expression for a sum from 1 to n over all matches.

It is unclear what an extension to three dimensions would mean.

 

[Duhoc]

I worked out the answer with a mathematician earlier today. I will try to post it using math symbols the best I can.
n-1
11 x nC2 + 9Σ 10superscript i-1 x (n-i + 1)C2
i=2

Please review this to see if it agrees with your answer. I will put up some calculations later as it is late and I have work tomorrow.

 

[Duhoc]

I worked out the answer with a mathematician earlier today. I will try to post it using math symbols the best I can.
n-1

I worked out the answer with a mathematician earlier today. I will try to post it using math symbols the best I can.
n-1
11 x nC2 + 9Σ 10superscript i-1 x (n-i + 1)C2
i=2

Please review this to see if it agrees with your answer. I will put up some calculations later as it is late and I have work tomorrow.

the n-1 and i=2 should be above and below the summation sign, it didnt come out well
11 x nC2 + 9Σ 10superscript i-1 x (n-i + 1)C2
i=2

Please review this to see if it agrees with your answer. I will put up some calculations later as it is late and I have work tomorrow.[/QUOT

 

[Duhoc]

another try at math formatting. anyone who can correct i would be most gratified.

11 x nC2 + 9∑10^i-1 x (n-i +1)C2

beneath the sigma i=2 above the sigma n-1

 

[Duhoc]

11 x nC2 + 9∑_i=2^n-1 10^i-1 x (n-i + 1)C2

Here is the formula using the formatting the best I could. I have included a calculation of a 10 space grid of 11 dots with 5 rows.

11 x 5C2 + 9 ∑⁴_i=2 10^4-1 x (5-2 + 1)C2

simplifying

110 + 9(10 x 4c2 + 10² x 3C2 + 10³ x 2C2)

simplifying

110 + 9(60 +300 +1000) or

110 + 9(1360)= 12,350 coincisions

Would someone like to use the formula to calculate the coincisions of 6 rows; 7rows; 8rows; 9rows; 10rows.

I thought of this problem in conjunction with thoughts I had regarding symmetry. I posted it before I could ask my neighbor who, yes, is a PhD in math. But I would like to develop the idea further. So a subsequent problem is, what would the formula be if there were any number of spaces rather than ten.

 

[mfb]

Would someone like to use the formula to calculate the coincisions of 6 rows; 7rows; 8rows; 9rows; 10rows.

Just plug it into WolframAlpha.

So a subsequent problem is, what would the formula be if there were any number of spaces rather than ten.

Replace 10 in the formulas by a different number (and 11 by 1 larger than the new number).

This forum supports LaTeX, by the way.
$$11 {n \choose 2} + 9 \sum_{i=2}^{n-1} 10^{i-1} {n-i+1 \choose 2}$$

 

[Duhoc]

I think that the general formula would take this form;

$$m+1 {n \choose 2} + m-1 \sum_{i=2}^{n-1} m^{i-1} {n-i+1 \choose 2}$$

where m is the number of spaces in the matrix and i the number of rows

the calculation for 6 rows where m =10 and i=6

For 6 rows
11 x 6C2 + 9(10 x 5C2 + 100 x 4C2 +1000 x 3C2 + 10,000 x 2C2
11 x 15 + 9(10 x 10 + 100 x 6 + 1000 x 3 + 10,000 x 1 =
1157 + 9(100 + 600 +3000 + 10000) = 124,457
and the original question

To extend our problem, let’s say we add two additional dimensions. We start with 11 dots and ten spaces and construct a cube with identical lines. Then we join all the dots with identical to form a grid. Next we divide the lines between any intersection into ten spaces and construct a grid within our first grid connecting these points. This grid is one order of magnitude more resolved than the original. We repeat the process for successive orders of magnitude. We shall define a coincision as any intersection which combines 2 intersections of three lines. What is the number of coincisions for any number of orders of magnitude we add.