BrainDen.com - Brain Teasers
• 0

## Question

Let n = a positive integer.

Suppose you choose n distinct points on a line.  The distance between

any pair of points is irrelevant.

A "curve" is either:

1) an individual point

2) a set of at least two points

3) an individual line segment

4) a set of at least two line segments

5) some combination of the above

I will label the points with A, B, C, ..., Y, Z, AA, AB, ..., and so on

as needed, consecutively from left to right, as we see them on

the screen.

If a line segment contains more than two points (recall that these are

discrete), then they will be labeled with only their endpoints.  Each

"curve" in a list will be separated by a comma.  The ordering in the

list is irrelevant.

The topic in this post involves the unordered listing and number of

the total of discrete "curves" in two dimensions for n distinct points,

where n is greater than or equal to one.

Examples:

--------------

n = 1

<----------------- A ---------------->

List:  {A}

Total:  1

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

n = 2

<-------------- A ----------- B ------------->

List:  {A}, {B}, {A, B}, {AB}

Total:  4

Note:  Here, you cannot have {A, AB}, {B, AB}, or {A, B, AB},

because neither point A nor point B is isolated once you

identify AB as a line segment in the set.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

n = 3

<-------- A -------- B -------------- C ----------->

List of points only:  {A}, {B}, {C}, {A, B}, {A, C}, {B, C}, {A, B, C}

List of line segments only: {AB}, {BC}, {AC}

List of points and line segments mixed:  {A, BC}, {AB, C}

Total:  12

Note:  Here, you cannot have {B, AC}, because point B is not

an isolated point.  It is part of line segment AC, and AC has

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Puzzle:  Compute the total number of "curves" for n = 4.

*** Optional additional question:  If you continue on getting

totals for n = 5, 6, 7, 8, ..., you will get a sequence that might

suggest a pattern to you.

As with all sequences, there are an infinite number of pos-

sibilities for a formula.  However, there is a formula that I have

in mind.  Whatever formula you get, do not attempt to

## Recommended Posts

• 0

Fibonacci(2n+1)-1

##### Share on other sites
• 0

(2n-1) + ((n2-n)/2) + ((3n+1 - 2n+3 + 6 + (-1)n+1)/12)

Validated out to n=5 so far...I'm pretty sure on the first two parts of that formula...it's the last/third that I'm a little questionable on...and if that's correct, here are the values up to 9:

n=1: 1

n=2: 4
n=3: 12
n=4: 31
n=5: 81
n=6: 218
n=7: 610
n=8: 1753
n=9: 5127

Edited by Pickett

##### Share on other sites
• 0

bonanova,

the main puzzle asks for the answer for when n = 4.  Maybe you kept it to yourself.

Did you have the value for n = 4?

Pickett,

you didn't get a confirmation either way for the total for n = 4, before going into more

calculations for the totals for larger n and then working on a formula.

The values for n = 4, 5, ... are different.

In the following spoiler, I show the listing and the total for n = 4:

n = 4

<---------- A --------- B ------------ C ---------------- D ------------->

list of points only:  {A}, {B}, {C}, {D}, {A, B}, {A, C}, {A, D}, {B, C}, {B, D}, {C, D}

{A, B, C}, {A, B, D}, {A, C, D}, {B, C, D}, {A, B, C, D}

list of line segments only:  {AB}, {BC}, {CD}, {AB, CD}, {AC}, {BD}, {AD}

list of points and line segments mixed:  {A, BC}, {A, CD}, {A, BD}, {B, CD},

{AB, C}, {AB, D}, {BC, D}, {AC, D}, {A, B, CD}, {A, BC, D}, {AB, C, D}

Total:  33

Edited by Perhaps check it again

##### Share on other sites
• 0

To follow up to my prior post, I will show the listing and the total for n = 5:

n = 5:

<------ A --------- B ---------- C -------------- D --------- E ------------>

points only:  {A}, {B}, {C}, {D}, {E}, {A, B}, {A, C}, {A, D}, {A, E}, {B, C}, {B, D}, {B, E},

{C, D}, {C, E}, {D, E}, {A, B, C}, {A, B, D}, {A, B, E}, {A, C, D}, {A, C, E}, {A, D, E},

{B, C, D}, {B, C, E}, {B, D, E}, {C, D, E},  {A, B, C, D}, {A, B, C, E}, {A, B, D, E},

{A, C, D, E}, {B, C, D, E}, {A, B, C, D, E}

line segments only:  {AB}, {BC}, {CD}, {DE}, {AB, CD}, {AB, DE}, {BC, DE}, {AC},

{BD}, {CE}, {AB, CE}, {AC, DE}, {AD}, {BE}, {AE}

points and line segments mixed:  {A, BC}, {A, CD}, {A, DE}, {B, CD}, {B, DE}, {AB, C},

{C, DE}, {AB, D}, {BC, D}, {AB, E}, {BC, E}, {CD, E}, {A, BD}, {A, CE}, {A, BC, DE},

{B, CE}, {AB, C, DE}, {AC, D}, {AC, E}, {BD, E}, {AB, CD, E}, {A, BE}, {AD, E},

{A, B, CD}, {A, B, DE}, {A, C, DE}, {A, BC, D}, {A, BC, E}, {A, CD, E}, {B, C, DE},

{B, CD, E}, {AB, C, D}, {AB, C, E}, {AB, D, E}, {BC, D, E}, {A, B, C, DE},

{A, B, CD, E}, {A, BC, D, E}, {AB, C, D, E}, {AC, D, E}, {A, BD, E}, {A, B, CE}

Total:  88

Reminder:  The total for n = 4 is actually:

33.

Edited by Perhaps check it again

##### Share on other sites
• 0

"curve" sequence [Fibonacci (2n+1)-1 : n ∈ ℤ

+ ] 1, 4, 12, 33, 88, ...

n = 4
List of points only:
{A}, {B}, {C}, {D}, {A,B}, {A,C}, {A,D}, {B,C}, {B,D}, {C,D}, {A,B,C}, {A,B,D}, {A,C,D}, {B,C,D}, {A,B,C,D}

List of line segments only:
{AB}, {AC}, {AD}, {BC}, {BD}, {CD}, {AB,CD}

List of points and line segments mixed:
{AB,C}, {AB,D} {A,BC}, {BC,D}, {A,CD}, {B,CD}, {A,BD}, {AC,D), {A,B,CD}, {A,BC,D}, {AB,C,D}

##### Share on other sites
• 0

witzar, I clicked yours as "Mark Solved," because it's posted before the next poster's,

and you both show the same formula.

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account. ×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×