1
$\begingroup$

The problem is as follows:

The figure below shows a triangular arrangement with a set of numbers. Each time you read a number, you cannot repeat the same digit and the distance between the digits must be the same, and the minimum distance possible. How many different ways can the number $5556789$ be read?

Sketch of the problem.

Supposedly the answer is $256$.

I attempted to assign a small number by counting the ways going right and left a-la Pascal triangle of combinatorics.

Sketch of the solution

Which would mean that the number of possibilities will result from summing the numbers at the base of the triangle:

$1+6+15+20+15+6+1=64$

Therefore I end up with $64$.

But this doesn't seem to be the answer. Can somebody tell me exactly what I am misunderstanding? How can I arrive to the right answer and more importantly how to do this? Please provide some graphic or visual aid with your answer to help me understand your solution.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
1
$\begingroup$

I'm no expert in combinatorics, but it looks like the answer you came up with is valid for the number $556789$, whereas the problem states that you are to make the number $5556789$ (there's an extra $5$ in there).

I expect that if you factor in that extra $5$, you'll get an answer of 256.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Yes, this looks right, OP can repeat a similar procedure where the blue numbers in the second row are 5 6 5 instead of 1 2 1 $\endgroup$
    – hexomino
    Commented Dec 19, 2019 at 17:52
  • $\begingroup$ @hexomino If had I added 5 6 5 in the second row then how would I had filled the rest of the triangle?. $\endgroup$
    – Chris Steinbeck Bell
    Commented Dec 21, 2019 at 3:09
  • $\begingroup$ @Chris You can get the three 5's by travelling horizontally for one step, or by starting on the second row, backtracking to the first, and then heading straight down the triangle. $\endgroup$
    – GentlePurpleRain
    Commented Dec 21, 2019 at 3:26
  • $\begingroup$ @GentlePurpleRain Then how do I get account for all the ways? I can't make the same logic as used in Pascal's. How should I put those numbers?. $\endgroup$
    – Chris Steinbeck Bell
    Commented Dec 21, 2019 at 3:29
  • $\begingroup$ Chris, as I mentioned in my answer, I'm no expert in combinatorics. Perhaps @hexomino would have more insight? $\endgroup$
    – GentlePurpleRain
    Commented Dec 21, 2019 at 6:29
1
$\begingroup$

I had trouble understanding the problem statement. It looks like it was translated at some point.

How I understand it, you must follow a path that reads the number, moving in any direction, but not reusing any digit, and moving only to contiguous digits.

The solution is as follows:

You must at some point reach a digit 5 followed by a 6.
So the third 5 must be on the 2nd row. From there you go down.

To count the total number of paths, you can do as follows:
Find out in how many ways you can en ona 5 in the 2nd row after a sequence 5-5-5. Then find out in how many ways you can complete the sequence with ...-6-7-8-9. The total number of paths is the product of these 2 numbers.

There are 5 ways to reach the left or the right 5 of row 3 after reading 5-5-5. There are 6 ways to end up in the centre 5 of row 3 after seeing 5-5-5. Neil's answer does a good job at showing how to count it. That is a total of 16 paths for the first 3 digits (the fives).

From any of these 5, your only choice to do ...-6-7-8-9 is to go down, either left or right at every step. You have 4 times 2 possibilities, that is $2^4 = 16$ ways to complete the sequence.

The total number of paths is the product of these numbers, that is $16 \times 16 = 256$.

Improve this answer
$\endgroup$
0
$\begingroup$

If i understand the problem corectly, it seems your reasoning is that you cant go "up" in your diagram, nor can you start at the second row.

if you start with all the fives of the second row, or start with the middle 5 of row two, go up then down, that is two additional ways for each extremity of the second row, if you find other ways for the middle 5 of row 2, you might end up with blue numbers being 5-6-5, which then double for each row, and eventually en up at 256 when summed

As you wanted a view of all the 5 possible paths for the leftmost 5 : 16 paths on row 2

as for a generalization, i don't really know, pascal triangle is good if your number can only be read from top to bottom, but as soon as you go up, or if you can start on another row than the first (think palindromic numbers, or a number composed oly of 10 times the same digit), then the numbers are going to be much greater.

Improve this answer
$\endgroup$
7
  • $\begingroup$ @GentlePurpleRain I'm trying very hard to understand what you mean by your explanation. Perhaps can you add a diagram so I could understand better?. $\endgroup$
    – Chris Steinbeck Bell
    Commented Dec 21, 2019 at 3:08
  • $\begingroup$ @Chris I'm not sure if you meant this for me, since you put it on Neil's answer, not mine... $\endgroup$
    – GentlePurpleRain
    Commented Dec 21, 2019 at 3:20
  • $\begingroup$ @GentlePurpleRain It was referring to Neil's answer. But again I'm not getting the idea of adding the extra $5$. I mean, I understand that to get the number I have to return a step behind, but if I do that I end up getting four times digit $5$ and not three as requested. $\endgroup$
    – Chris Steinbeck Bell
    Commented Dec 21, 2019 at 3:24
  • $\begingroup$ @Neil Howdy! It's been like a year after this answer has been posted and I'm still not getting the idea. How did you got to those five ways for the five in the leftmost part in the second row?. Can you explain in more details how did you got to them?. I'm still struggling with that part. I've already counted the ways for that number but I'm getting four different ways not five, how did you do that account for also the five in the middle?. $\endgroup$
    – Chris Steinbeck Bell
    Commented Nov 9, 2020 at 3:57
  • $\begingroup$ @ChrisSteinbeckBell edited my answer with a picture, but the generalization to calculate the number in an automatic way without bruteforcing with a program is beyond my graph knowledge. $\endgroup$
    – Neil
    Commented Nov 11, 2020 at 9:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.