Jump to content
BrainDen.com - Brain Teasers
  • 0
Perhaps check it again

Number of discrete "curves" in two dimensions

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

already been listed.

 

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

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

 

 

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

prove it.  Just type the formula in your reply.

 

Share this post


Link to post
Share on other sites

7 answers to this question

Recommended Posts

  • 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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

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

Loading...

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...