Longest possible subsequence present with a given condition

Clash Royale CLAN TAG#URR8PPP

up vote
0
down vote

favorite

Let a Domino represent an ordered pair of distinct positive integers. A proper sequence of dominos is a list of distinct dominos in which the first coordinate of each pair after the first equals the second coordinate of the immediately preceding pair, and in which $(i,j)$ and $(j,i)$ do not both appear for any $i$ and $j$. Let $D_40$ be the set of all dominos whose coordinates are no larger than $40$. How can I find the longest proper sequence of dominos using the dominos of $D_40$?

sequences-and-series combinatorics combinations

share|cite|improve this question

edited Jul 25 at 17:46

Key Flex

4,258423

asked Jul 23 at 10:58

saisanjeev

372210

add a comment | 

up vote
0
down vote

favorite

Let a Domino represent an ordered pair of distinct positive integers. A proper sequence of dominos is a list of distinct dominos in which the first coordinate of each pair after the first equals the second coordinate of the immediately preceding pair, and in which $(i,j)$ and $(j,i)$ do not both appear for any $i$ and $j$. Let $D_40$ be the set of all dominos whose coordinates are no larger than $40$. How can I find the longest proper sequence of dominos using the dominos of $D_40$?

sequences-and-series combinatorics combinations

share|cite|improve this question

edited Jul 25 at 17:46

Key Flex

4,258423

asked Jul 23 at 10:58

saisanjeev

372210

add a comment | 

up vote
0
down vote

favorite

up vote
0
down vote

favorite

Let a Domino represent an ordered pair of distinct positive integers. A proper sequence of dominos is a list of distinct dominos in which the first coordinate of each pair after the first equals the second coordinate of the immediately preceding pair, and in which $(i,j)$ and $(j,i)$ do not both appear for any $i$ and $j$. Let $D_40$ be the set of all dominos whose coordinates are no larger than $40$. How can I find the longest proper sequence of dominos using the dominos of $D_40$?

sequences-and-series combinatorics combinations

share|cite|improve this question

edited Jul 25 at 17:46

Key Flex

4,258423

asked Jul 23 at 10:58

saisanjeev

372210

Let a Domino represent an ordered pair of distinct positive integers. A proper sequence of dominos is a list of distinct dominos in which the first coordinate of each pair after the first equals the second coordinate of the immediately preceding pair, and in which $(i,j)$ and $(j,i)$ do not both appear for any $i$ and $j$. Let $D_40$ be the set of all dominos whose coordinates are no larger than $40$. How can I find the longest proper sequence of dominos using the dominos of $D_40$?

sequences-and-series combinatorics combinations

share|cite|improve this question

edited Jul 25 at 17:46

Key Flex

4,258423

asked Jul 23 at 10:58

saisanjeev

372210

share|cite|improve this question

share|cite|improve this question

edited Jul 25 at 17:46

Key Flex

4,258423

edited Jul 25 at 17:46

Key Flex

4,258423

edited Jul 25 at 17:46

Key Flex

4,258423

4,258423

asked Jul 23 at 10:58

saisanjeev

372210

asked Jul 23 at 10:58

saisanjeev

372210

asked Jul 23 at 10:58

saisanjeev

372210

372210

add a comment | 

add a comment | 

1 Answer
1

active

oldest

votes

up vote
0
down vote

First draw a domino set of $40$ points which are connected to each other. These connections represent the dominoes.

Then we have all the even number of segments coming from each connected point except for $0$ and $2$ because it has an odd number of segments from the point. Note that every time when we go to vertex, it means that we are leaving the vertex. So when we reach every vertex it is equivalent to adding $2$ more segments which means that the degree of each vertex should be even leaving the endpoints. Since there are $39$ segments coming from each point it is impossible to touch every segment.

But you can get up to $38$ on each segment because you go in to the point then out on a different segment. Counting going out from the starting and ending at the ending point we have $dfrac30times40+22=761$

share|cite|improve this answer

edited Jul 23 at 16:04

answered Jul 23 at 11:40

Key Flex

4,258423

• 
  
  
  

  
  

  
  
  
  
  
  

  
  How did you arrive at the first argument?
  – saisanjeev
  Jul 29 at 9:49
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @saisanjeev From the question "A proper sequence of dominos is a list of distinct dominos in which the first coordinate of each pair after the first equals the second coordinate of the immediately preceding pair, and in which (i,j) and (j,i) do not both appear for any i and j. "
  – Key Flex
  Jul 29 at 12:02
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2860226%2flongest-possible-subsequence-present-with-a-given-condition%23new-answer', 'question_page');

);

Post as a guest

Name Email

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
0
down vote

First draw a domino set of $40$ points which are connected to each other. These connections represent the dominoes.

Then we have all the even number of segments coming from each connected point except for $0$ and $2$ because it has an odd number of segments from the point. Note that every time when we go to vertex, it means that we are leaving the vertex. So when we reach every vertex it is equivalent to adding $2$ more segments which means that the degree of each vertex should be even leaving the endpoints. Since there are $39$ segments coming from each point it is impossible to touch every segment.

But you can get up to $38$ on each segment because you go in to the point then out on a different segment. Counting going out from the starting and ending at the ending point we have $dfrac30times40+22=761$

share|cite|improve this answer

edited Jul 23 at 16:04

answered Jul 23 at 11:40

Key Flex

4,258423

• 
  
  
  

  
  

  
  
  
  
  
  

  
  How did you arrive at the first argument?
  – saisanjeev
  Jul 29 at 9:49
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @saisanjeev From the question "A proper sequence of dominos is a list of distinct dominos in which the first coordinate of each pair after the first equals the second coordinate of the immediately preceding pair, and in which (i,j) and (j,i) do not both appear for any i and j. "
  – Key Flex
  Jul 29 at 12:02
  

  
  
  
  

add a comment | 

up vote
0
down vote

First draw a domino set of $40$ points which are connected to each other. These connections represent the dominoes.

Then we have all the even number of segments coming from each connected point except for $0$ and $2$ because it has an odd number of segments from the point. Note that every time when we go to vertex, it means that we are leaving the vertex. So when we reach every vertex it is equivalent to adding $2$ more segments which means that the degree of each vertex should be even leaving the endpoints. Since there are $39$ segments coming from each point it is impossible to touch every segment.

But you can get up to $38$ on each segment because you go in to the point then out on a different segment. Counting going out from the starting and ending at the ending point we have $dfrac30times40+22=761$

share|cite|improve this answer

edited Jul 23 at 16:04

answered Jul 23 at 11:40

Key Flex

4,258423

• 
  
  
  

  
  

  
  
  
  
  
  

  
  How did you arrive at the first argument?
  – saisanjeev
  Jul 29 at 9:49
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @saisanjeev From the question "A proper sequence of dominos is a list of distinct dominos in which the first coordinate of each pair after the first equals the second coordinate of the immediately preceding pair, and in which (i,j) and (j,i) do not both appear for any i and j. "
  – Key Flex
  Jul 29 at 12:02
  

  
  
  
  

add a comment | 

up vote
0
down vote

up vote
0
down vote

First draw a domino set of $40$ points which are connected to each other. These connections represent the dominoes.

Then we have all the even number of segments coming from each connected point except for $0$ and $2$ because it has an odd number of segments from the point. Note that every time when we go to vertex, it means that we are leaving the vertex. So when we reach every vertex it is equivalent to adding $2$ more segments which means that the degree of each vertex should be even leaving the endpoints. Since there are $39$ segments coming from each point it is impossible to touch every segment.

But you can get up to $38$ on each segment because you go in to the point then out on a different segment. Counting going out from the starting and ending at the ending point we have $dfrac30times40+22=761$

share|cite|improve this answer

edited Jul 23 at 16:04

answered Jul 23 at 11:40

Key Flex

4,258423

First draw a domino set of $40$ points which are connected to each other. These connections represent the dominoes.

Then we have all the even number of segments coming from each connected point except for $0$ and $2$ because it has an odd number of segments from the point. Note that every time when we go to vertex, it means that we are leaving the vertex. So when we reach every vertex it is equivalent to adding $2$ more segments which means that the degree of each vertex should be even leaving the endpoints. Since there are $39$ segments coming from each point it is impossible to touch every segment.

But you can get up to $38$ on each segment because you go in to the point then out on a different segment. Counting going out from the starting and ending at the ending point we have $dfrac30times40+22=761$

share|cite|improve this answer

edited Jul 23 at 16:04

answered Jul 23 at 11:40

Key Flex

4,258423

share|cite|improve this answer

share|cite|improve this answer

edited Jul 23 at 16:04

edited Jul 23 at 16:04

edited Jul 23 at 16:04

answered Jul 23 at 11:40

Key Flex

4,258423

answered Jul 23 at 11:40

Key Flex

4,258423

answered Jul 23 at 11:40

Key Flex

4,258423

4,258423

• 
  
  
  

  
  

  
  
  
  
  
  

  
  How did you arrive at the first argument?
  – saisanjeev
  Jul 29 at 9:49
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @saisanjeev From the question "A proper sequence of dominos is a list of distinct dominos in which the first coordinate of each pair after the first equals the second coordinate of the immediately preceding pair, and in which (i,j) and (j,i) do not both appear for any i and j. "
  – Key Flex
  Jul 29 at 12:02
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  How did you arrive at the first argument?
  – saisanjeev
  Jul 29 at 9:49
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @saisanjeev From the question "A proper sequence of dominos is a list of distinct dominos in which the first coordinate of each pair after the first equals the second coordinate of the immediately preceding pair, and in which (i,j) and (j,i) do not both appear for any i and j. "
  – Key Flex
  Jul 29 at 12:02
  

  
  
  
  

How did you arrive at the first argument?
– saisanjeev
Jul 29 at 9:49

How did you arrive at the first argument?
– saisanjeev
Jul 29 at 9:49

@saisanjeev From the question "A proper sequence of dominos is a list of distinct dominos in which the first coordinate of each pair after the first equals the second coordinate of the immediately preceding pair, and in which (i,j) and (j,i) do not both appear for any i and j. "
– Key Flex
Jul 29 at 12:02

@saisanjeev From the question "A proper sequence of dominos is a list of distinct dominos in which the first coordinate of each pair after the first equals the second coordinate of the immediately preceding pair, and in which (i,j) and (j,i) do not both appear for any i and j. "
– Key Flex
Jul 29 at 12:02

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2860226%2flongest-possible-subsequence-present-with-a-given-condition%23new-answer', 'question_page');

);

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email