3
$\begingroup$

How many possible ways can you completely draw this figure?

enter image description here

Conditions:

1 - Once you start to draw you can’t take your pencil off of the paper.
2 - You can’t trace along a line already drawn.

$\endgroup$
8
$\begingroup$

This is really a job for a computer rather than a human being, but never mind. (I will check my answer with a computer after posting it...)

[EDITED to add:] Looks like I missed exactly 48 routes. Corrections are below. I confess that I used a computer to check the total and help find what I'd missed.

You have to start at one of the bottom corners and end at the other. (Because any vertex of odd degree has to be the start or the end of the path, and there are exactly two of those.) Without loss of generality let's start at bottom left and end at bottom right; this will give us exactly half of the paths.

Call the vertices of the square, reading clockwise from bottom left, ABCD; and call the middle of the square X. We always start at A. We must visit X twice, with each of A,B,C,D coming before or after it just once. Call two of A,B,C,D "partners" if we visit one of them, then X, then the other. We may have A,B and C,D partners; or A,C and B,D; or A,D and B,C.

If A,B and C,D are partners, this is equivalent to a graph without X but with extra AB,CD edges. We will go between each of the pairs {A,B}, {B,C}, {C,D} exactly twice, so if we don't bother to record which edge we choose each time then we will count exactly 1/8 of the paths. Now we must start ABA (which must continue DCBCD) or ABC (which may continue BADCD or DCBAD) or AD (which must continue CBABCD). That's 4 paths, or 32 when we bother to distinguish "parallel" edges.

[EDITED to add:] I missed ABCDABCD. So 40 rather than 32 paths.

If A,D and B,C are partners, this is equivalent to a graph without X but with extra AD,BC edges. We will go between {A,D} exactly twice and between {B,C} exactly three times, so if we don't bother to record which edge we choose each time then we will count exactly 1/12 of the paths. Now we must start ABC (in which case we can't proceed to D because then we can't get back to B,C, so we must continue BCDAD) or ADA (in which case we must continue BCBCD) or ADCB (in which case again we can't proceed to A so must continue CBAD). That's 3 paths, or 36 when we bother to distinguish "parallel" edges.

If A,C and B,C are partners, this is equivalent to the graph we already had with the reinterpretation that the diagonals are two separate edges and don't meet in the middle. We will travel exactly twice between B,C, so if we don't distinguish between the "parallel" edges between those vertices we will count exactly 1/2 of the paths. Now there's a symmetry between B,C so if we also assume we visit B before C then we will count exactly 1/4 of the paths instead. Now our possible beginnings are ABC, ABD, ADB, and by mere brute force I think our options are ABCBDCAD, ABCBDACD; ABDACBCD, ABDCBCAD; ADBACBCD, ADBCABCD, ADBCBACD. That's 7 paths, or 28 after un-ignoring those symmetries.

[EDITED to add:] I missed rather a lot here. After ABC we can go straight to D and then we can traverse the remaining four vertices in either direction (two more paths with symmetries ignored -> 8 more in total). Or we can go to A, then D, and traverse the remaining three in either directions (another 2/8 more). After ABD or ADB there are just the options I listed above. So I'm 16 short: not 28 but 44.

In summary,

we have a total of 40+36+44=120 routes. And that was all starting at A rather than at D, so the total number is twice that or 240.

Here, in case anyone cares, is the computer code, in Python. It's not very efficient, but it doesn't need to be: it was much faster than I was, and got the right answer straight away :-).

def e(prefix, target, edges):
    last = prefix[-1]
    if not edges:
        if last == target: yield prefix
        return
    for edge in edges:
        if last in edge:
            if last==edge[0]: other=edge[1]
            else: other=edge[0]
            yield from e(prefix+other, target, edges-{edge})

print(list(e('A','D',{'AB','BP','PC','BQ','QC','CD','AD','AX','BX','CX','DX'})))
| improve this answer | |
$\endgroup$
  • $\begingroup$ I can confirm this is the correct answer... $\endgroup$ – Dr Xorile Feb 8 '19 at 19:50
5
$\begingroup$

I've (very quickly) found 36:

enter image description here Each can be reversed and flipped over the y-axis

Edit: I've exhausted my ideas and effort for this, someone feel free to add more!

| improve this answer | |
$\endgroup$
  • $\begingroup$ I've never thought about using the cross in the centre as a turning point and doing >< instead of x.... $\endgroup$ – AHKieran Feb 8 '19 at 15:05
  • $\begingroup$ @AHKieran yeah! I wasn't sure if it would be possible but wanted to see! $\endgroup$ – eye_am_groot Feb 8 '19 at 15:11
4
$\begingroup$

I went ahead and did this with a computer. Of course, @Gareth had already done it by then. I can confirm his answer of:

240 (Two times the 120 graphed below which all start at the bottom left)

Here's a computer-generated version of the graphs:

All Euler Paths


Old answer and salient warning about trying to go through things systematically before coffee:

I make it

72 (these and their reverse and one that I missed which should be in the third row between 3 and 4)

They are

paths

| improve this answer | |
$\endgroup$
  • $\begingroup$ You are everywhere!,!!!! $\endgroup$ – user56760 Feb 14 '19 at 16:48
1
$\begingroup$

Infinite. You can fold the paper, use other papers to traverse onto and off of, etc.

I've blocked myself in...

But with a fold...

Manage to complete the drawing without lifting the pen.

And here, see how I've used another paper to do some random stuff between step 3 and 4.

The rules do not make such a strategy illegal, therefore such a solution is valid. :)

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Interesting idea... would you be able to demonstrate a method of actually doing so, so that it is more clear what exactly you mean? $\endgroup$ – mmking Feb 9 '19 at 2:28
  • $\begingroup$ @Tylerhoppe please demonstrate your anwere more specifically $\endgroup$ – user56760 Feb 9 '19 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy