set of digits?

Question

i have a set of digits S={ 1 , 2, 3, 4, 5 }

Now, i want to choose 3 digits from that set S such that addintion of ANY two digits > third digit

one such correct answer is , {2,3,4} because 2+3 > 4 or 3+4 >2 or 2+4 > 3

I
one such wrong answer is {1,2,3}
because It does not satisfy.... as 1+2 !>3


I dont know how do i start .

I need a process which will help me to pick up all those correct subsets ....i dont want to miss any subset.



so, should i start scanning the elements from the beginning and write in the notebook and then i'll scan again from the next element and write in notebook and then try to add and see whether this exceeds the next ? I dont think this is a good process and i am afraid that i might miss some sub-set if i try to solve this way.


how do i start ?

Mr dread ,

you answer is correct.

but how did you write so many sub sets ....can you please explain it more.

thank you

i have to gather all the subsets first before rulling out any sub set.

and gathering all these subsets is a difficult task to me

Answer 1

First, narrow the possibilities. If any of these triples fail the inequality, the failure will occur when the largest number is on the right. If the triple meets the inequality in that case, it will meet the inequality with one of the smaller numbers on the right. Therefore, you can test each of the triples by testing this one inequality.

You can further reduce the possibilities by noting that if one set of triples fails, the other triples with a larger big number will also necessarily fail. This means, for example, if

1 + 2 !> 3, then
1 + 2 !> 4 and
1 + 2 !> 5 also.

It also turns out that, for any n,

1 + n !> n+1.

Combining these two principles, any combination with 1 as the smallest number cannot meet the inequality.

This leaves a small number of triples to work with, namely,

2, 3, 4,
2, 3, 5,
2, 4, 5, and
3, 4, 5.

of these, only the combination 2, 3, 5 fails to meet the conditions.

If you had a set of k contiguous digits as the set you started with, you could also use the concept that the largest number cannot be as large as the sum of the two smaller ones. From this, you can come up with a formula for determining the number of combinations of digits from 1 to k that will meet your conditions.

Answer 2

There are 60 3-digit subsets of digits {1,2,3,4,5}
Half of these are essentially duplicates (1 + 2 = 2 + 1), leaving 30 choices. Of these, 23 fit the criteria (a + b) > c, 4 result in equality, and 3 result in (a + b) < c. All 60 subsets are listed below.
5 + 4 > 3, 4 + 5 > 3
5 + 4 > 2, 4 + 5 > 2
5 + 4 > 1, 4 + 5 > 1
5 + 3 > 4, 3 + 5 > 4
5 + 3 > 2, 3 + 5 > 2
5 + 3 > 1, 3 + 5 > 1
5 + 2 > 4, 2 + 5 > 4
5 + 2 > 3, 2 + 5 > 3
5 + 2 > 1, 2 + 5 > 1
5 + 1 > 4, 1 + 5 > 4
5 + 1 > 3, 1 + 5 > 3
5 + 1 > 2, 1 + 5 > 2
4 + 3 > 5, 3 + 4 > 5
4 + 3 > 2, 3 + 4 > 2
4 + 3 > 1, 3 + 4 > 1
4 + 2 > 5, 2 + 4 > 5
4 + 2 > 3, 2 + 4 > 3
4 + 2 > 1, 2 + 4 > 1
4 + 1 > 3, 1 + 4 > 3
4 + 1 > 2, 1 + 4 > 2
3 + 2 > 4, 2 + 3 > 4
3 + 2 > 1, 2 + 3 > 1
3 + 1 > 2, 1 + 3 > 2
4 + 1 = 5, 1 + 4 = 5
3 + 2 = 5, 2 + 3 = 5
3 + 1 = 4, 1 + 3 = 4
2 + 1 = 3, 1 + 2 = 3
3 + 1 < 5, 1 + 3 < 5
2 + 1 < 5, 1 + 2 < 5
2 + 1 < 4, 1 + 2 < 4

Answer 3

There only 10 combinations (5 taken 3 at a time) so it's not that hard to list all subsets, and when you apply the rule,

123 no
124 no
125 no
134 no
135 no
145 no
234 yes
235 no
245 yes
345 yes

Answer 4

I'm thinking we'll start as if it is a probability question (or, more specifically, a combinatorics question since order is not important in the selection set).

There are 5 choose 3 (5C3) different sets we can select, which is 5!/(3! * 2!) = 10

So it is quite easy to enumerate all 10 sets. Working left to right we have them like so:

1,2,3
1,2,4
1,2,5
1,3,4
1,3,5
1,4,5
2,3,4
2,3,5
2,4,5
3,4,5

Doing the math, you can see fairly quickly that none of the sets including the digit 1 meet the criteria (by adding the first two numbers and getting a sum that is less than or equal to the third).

We can use the same left-to-right scanning that we used to enumerate all of the sets, to enumerate all of the additions. Once again order is not important, so each set produces 3C2 = 3!/(2! * 1!) = 3 different additions.

2,3,4

2+3 > 4, 2+4 > 3, 3+4 > 2

2,3,5

2+3 = 5 (we can stop), 2+5, 3+5

2,4,5

2+4 > 5, 2+5 > 4, 4+5 > 2

3,4,5

3+4 > 5, 3+5 > 4, 4+5 > 3

So we have three sets that meet the criteria: {2,3,4}, {2,4,5}, and {3,4,5}.


Further information on Hot to Derive the Sets

Basically I start with the first three digits and create a set:

{1,2,3}

Then I advance the third digit as far as I can until I have derived all of the sets containing {1,2} as the first two members:

{1,2,4}
{1,2,5}

Then I repeat this procedure, this time starting by advancing the second digit. So now I'm looking for all sets containing {1,3} as the first two members (notice that we don't start with {1,3,2}; since order is not important we do not have to back track to any lower numbers).

Proceeding like we did with the sets starting with {1,2}, we advance the third digit as far as possible:

{1,3,4}
{1,3,5}

Now we can advance the second digit again, and look for all of the sets starting with {1,4}. Proceeding as before, we advance the third digit as far as possible (in this case, there is only one set since 5 is the highest number):

{1,4,5}

If we try to again advance the second digit, you will notice there will not be enough numbers left to complete any sets:

{1,5,?}

Therefore we can now advance the first digit, and look for all of the sets starting with {2,3} (once again, we don't backtrack to 1 because order is important; i.e. the set {1,2,3} is equivalent to {2,3,1}). Once you have a new set of two, you advance the third digit as far as possible (as before):

{2,3,4}
{2,3,5}

Now we advance the second digit, and look for all sets starting with {2,4}. Proceeding by advancing the third digit as far as possible yields only the following (since 5 is the highest number):

{2,4,5}

Once again, we find our terminating condition by trying to advance the second digit:

{2,5,?}

So we advance the first digit again, and look for all sets starting with {3,4}. Once again this yields only one set:

{3,4,5}

So you can kind of tell my general algorithm is depth-first, where I advance the last digit as much as possible. Then I advance the second-to-last digit once and repeat the last digit advancement. Then repeat this second-to-last digit single advancement until you cannot create any more sets. Then it's time to advance the third-to-last digit once, and repeat (starting with the second-digit advancement).

Answer 5

purple.....yeah. Good luck with that. I have NO idea....but hey, think of happy ponies and purple things...then find someone who knows how this is supposed to be solved.....

Now, what was the question?