Tjyylli

Accountant/ lawyer will not return my call

How did Alan Turing break the enigma code using the hint given by the lady in the bar?

The bar has been raised

Is there an equal sign with wider gap?

A word meaning “to take something with you since it is not difficult for you anyway”

Space in array system equations

Do I really need to have a scientific explanation for my premise?

Good for you! in Russian

Rejected in 4th interview round citing insufficient years of experience

Why would a jet engine that runs at temps excess of 2000°C burn when it crashes?

In the late 1940’s to early 1950’s what technology was available that could melt a LOT of ice?

Making a sword in the stone, in a medieval world without magic

What to do when during a meeting client people start to fight (even physically) with each others?

Latest web browser compatible with Windows 98

Subset counting for even numbers

How to pass a string to a command that expects a file?

Grey hair or white hair

Single word request: Harming the benefactor

Force user to remove USB token

Is there an elementary proof that there are infinitely many primes that are *not* completely split in an abelian extension?

infinitive telling the purpose

How do you like my writing?

Good allowance savings plan?

Reverse string, can I make it faster?

Subset counting for even numbers

Get the number of subset.How many non empty subsets of {1, 2, …, n} satisfy that the sum of their elements is even?how many $7$ digit numbers can be formed using $1,2,3,4,5,6,7,8,9,0$Prove that all numbers in a sequence are equalcantor diagonal argument for even numbersSets Whose Elements Sum to an Even IntegerCounting - $9$ digit number consisting of $5$ odd and $4$ even digits, not sure how to do the 2nd stepSum of elements in a subsetNumber of ways to color the numbers from 1 to 9 choosing from 3 colors for each one, such that no two numbers whose sum is odd are the same colorChoosing three distinct numbers giving even sum.

1

$begingroup$

Let $S$ be a set of twelve integers ${1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}$. How many subsets of $S$ are there such that the sum of all the elements in the subset is an odd number?

Here's what I tried. There are $2^{12}=4096$ ways to create a subset from $S$. I tried to find the number of what I call "even" subsets, or subsets whose elements only summed to even numbers. I divided $S$ into two subsets, one for all even numbers, and one for all odd numbers, knowing that all the subsets of those two subsets must have an even sum. Counting the sum and subtracting from $4096$, I get $2^{12}-2^6-2^6=3968$. However, now I realize that there are more ways to create "even" subsets, for example, two odds, four evens. I am now stuck. Can someone help?

combinatorics number-theory elementary-set-theory

share|cite|improve this question

asked 41 mins ago

A RA R

435

$endgroup$

add a comment | 

1

$begingroup$

Let $S$ be a set of twelve integers ${1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}$. How many subsets of $S$ are there such that the sum of all the elements in the subset is an odd number?

Here's what I tried. There are $2^{12}=4096$ ways to create a subset from $S$. I tried to find the number of what I call "even" subsets, or subsets whose elements only summed to even numbers. I divided $S$ into two subsets, one for all even numbers, and one for all odd numbers, knowing that all the subsets of those two subsets must have an even sum. Counting the sum and subtracting from $4096$, I get $2^{12}-2^6-2^6=3968$. However, now I realize that there are more ways to create "even" subsets, for example, two odds, four evens. I am now stuck. Can someone help?

combinatorics number-theory elementary-set-theory

share|cite|improve this question

asked 41 mins ago

A RA R

435

$endgroup$

add a comment | 

$begingroup$

Let $S$ be a set of twelve integers ${1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}$. How many subsets of $S$ are there such that the sum of all the elements in the subset is an odd number?

Here's what I tried. There are $2^{12}=4096$ ways to create a subset from $S$. I tried to find the number of what I call "even" subsets, or subsets whose elements only summed to even numbers. I divided $S$ into two subsets, one for all even numbers, and one for all odd numbers, knowing that all the subsets of those two subsets must have an even sum. Counting the sum and subtracting from $4096$, I get $2^{12}-2^6-2^6=3968$. However, now I realize that there are more ways to create "even" subsets, for example, two odds, four evens. I am now stuck. Can someone help?

combinatorics number-theory elementary-set-theory

share|cite|improve this question

asked 41 mins ago

A RA R

435

$endgroup$

share|cite|improve this question

asked 41 mins ago

A RA R

435

share|cite|improve this question

asked 41 mins ago

A RA R

435

asked 41 mins ago

A RA R

435

asked 41 mins ago

A RA R

435

3 Answers
3

active

oldest

votes

5

$begingroup$

Split $S$ into the set of even numbers of $S$ and the set of odd numbers of $S$, what I'll call $E = {2,4,6,8,10,12}$ and $O = {1,3,5,7,9,11}$

Form your arbitrary subset of $S$ where the sum of elements is odd by selecting any subset of $E$ and unioning that with with any subset of an odd number of elements from $O$.

Apply the rule of product and conclude.

There are $2^6$ possible subsets of $E$ and there are $binom{6}{1}+binom{6}{3}+binom{6}{5} = 2^5$ subsets with an odd number of elements of $O$

---

Alternate explanation. First choose any subset of ${2,3,4,dots,12}$. If the sum is currently even, then include also $1$ with it. If the sum is currently odd, then don't include $1$. Convince yourself that you cover all cases exactly once each.

share|cite|improve this answer

answered 36 mins ago

JMoravitzJMoravitz

48.5k33987

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  That gets me $2^{11}=2048$ subsets. Thank you so much for your method!
  $endgroup$
  – A R
  26 mins ago
  
  
  

  
  
  
  

add a comment | 

2

$begingroup$

Hint:

If we sum up an odd number of odd integers, and however many even ones we wish with them, then the sum is always odd.

This can be justified by considering arithmetic and congruences modulo $2$ if you want to formally see this, but I feel like it's relatively self-evident just by trying a few examples.

Thus, you need to find the number of subsets of $S$ which contain an odd number of odd integers in them.

share|cite|improve this answer

answered 37 mins ago

Eevee TrainerEevee Trainer

7,80721339

$endgroup$

add a comment | 

0

$begingroup$

The credit for this strategy goes entirely to JMoravitz.

What I didn't realize earlier is that as long as there are an odd number of odd numbers in our subset, then we can get an odd numbers, no matter how many even numbers are in the subset. I will make the even and odd subsets separately to be $E={2, 4, 6, 8, 10, 12}$ and $O={1, 3, 5, 7, 9, 11}$. There are ${6choose1} + {6choose3} + {6choose5}=2^{5}=32$ ways to pick odd numbers. We can now pick as many evens as we wish, so we have $2^6$ ways to pick a subset. The union of the subset will just be the product of the two values, so we have $2^5 times 2^6=2^{11}=boxed{2048}$ subsets.

Thank you all so much for the help!

share|cite|improve this answer

answered 18 mins ago

A RA R

435

$endgroup$

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',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
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

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3145885%2fsubset-counting-for-even-numbers%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

5

$begingroup$

Split $S$ into the set of even numbers of $S$ and the set of odd numbers of $S$, what I'll call $E = {2,4,6,8,10,12}$ and $O = {1,3,5,7,9,11}$

Form your arbitrary subset of $S$ where the sum of elements is odd by selecting any subset of $E$ and unioning that with with any subset of an odd number of elements from $O$.

Apply the rule of product and conclude.

There are $2^6$ possible subsets of $E$ and there are $binom{6}{1}+binom{6}{3}+binom{6}{5} = 2^5$ subsets with an odd number of elements of $O$

---

Alternate explanation. First choose any subset of ${2,3,4,dots,12}$. If the sum is currently even, then include also $1$ with it. If the sum is currently odd, then don't include $1$. Convince yourself that you cover all cases exactly once each.

share|cite|improve this answer

answered 36 mins ago

JMoravitzJMoravitz

48.5k33987

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  That gets me $2^{11}=2048$ subsets. Thank you so much for your method!
  $endgroup$
  – A R
  26 mins ago
  
  
  

  
  
  
  

add a comment | 

5

$begingroup$

Split $S$ into the set of even numbers of $S$ and the set of odd numbers of $S$, what I'll call $E = {2,4,6,8,10,12}$ and $O = {1,3,5,7,9,11}$

Form your arbitrary subset of $S$ where the sum of elements is odd by selecting any subset of $E$ and unioning that with with any subset of an odd number of elements from $O$.

Apply the rule of product and conclude.

There are $2^6$ possible subsets of $E$ and there are $binom{6}{1}+binom{6}{3}+binom{6}{5} = 2^5$ subsets with an odd number of elements of $O$

---

Alternate explanation. First choose any subset of ${2,3,4,dots,12}$. If the sum is currently even, then include also $1$ with it. If the sum is currently odd, then don't include $1$. Convince yourself that you cover all cases exactly once each.

share|cite|improve this answer

answered 36 mins ago

JMoravitzJMoravitz

48.5k33987

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  That gets me $2^{11}=2048$ subsets. Thank you so much for your method!
  $endgroup$
  – A R
  26 mins ago
  
  
  

  
  
  
  

add a comment | 

$begingroup$

Split $S$ into the set of even numbers of $S$ and the set of odd numbers of $S$, what I'll call $E = {2,4,6,8,10,12}$ and $O = {1,3,5,7,9,11}$

Form your arbitrary subset of $S$ where the sum of elements is odd by selecting any subset of $E$ and unioning that with with any subset of an odd number of elements from $O$.

Apply the rule of product and conclude.

There are $2^6$ possible subsets of $E$ and there are $binom{6}{1}+binom{6}{3}+binom{6}{5} = 2^5$ subsets with an odd number of elements of $O$

---

Alternate explanation. First choose any subset of ${2,3,4,dots,12}$. If the sum is currently even, then include also $1$ with it. If the sum is currently odd, then don't include $1$. Convince yourself that you cover all cases exactly once each.

share|cite|improve this answer

answered 36 mins ago

JMoravitzJMoravitz

48.5k33987

$endgroup$

share|cite|improve this answer

answered 36 mins ago

JMoravitzJMoravitz

48.5k33987

answered 36 mins ago

JMoravitzJMoravitz

48.5k33987

answered 36 mins ago

JMoravitzJMoravitz

48.5k33987

2

$begingroup$

Hint:

If we sum up an odd number of odd integers, and however many even ones we wish with them, then the sum is always odd.

This can be justified by considering arithmetic and congruences modulo $2$ if you want to formally see this, but I feel like it's relatively self-evident just by trying a few examples.

Thus, you need to find the number of subsets of $S$ which contain an odd number of odd integers in them.

share|cite|improve this answer

answered 37 mins ago

Eevee TrainerEevee Trainer

7,80721339

$endgroup$

add a comment | 

2

$begingroup$

Hint:

If we sum up an odd number of odd integers, and however many even ones we wish with them, then the sum is always odd.

This can be justified by considering arithmetic and congruences modulo $2$ if you want to formally see this, but I feel like it's relatively self-evident just by trying a few examples.

Thus, you need to find the number of subsets of $S$ which contain an odd number of odd integers in them.

share|cite|improve this answer

answered 37 mins ago

Eevee TrainerEevee Trainer

7,80721339

$endgroup$

add a comment | 

$begingroup$

Hint:

If we sum up an odd number of odd integers, and however many even ones we wish with them, then the sum is always odd.

This can be justified by considering arithmetic and congruences modulo $2$ if you want to formally see this, but I feel like it's relatively self-evident just by trying a few examples.

Thus, you need to find the number of subsets of $S$ which contain an odd number of odd integers in them.

share|cite|improve this answer

answered 37 mins ago

Eevee TrainerEevee Trainer

7,80721339

$endgroup$

share|cite|improve this answer

answered 37 mins ago

Eevee TrainerEevee Trainer

7,80721339

answered 37 mins ago

Eevee TrainerEevee Trainer

7,80721339

answered 37 mins ago

Eevee TrainerEevee Trainer

7,80721339

0

$begingroup$

The credit for this strategy goes entirely to JMoravitz.

What I didn't realize earlier is that as long as there are an odd number of odd numbers in our subset, then we can get an odd numbers, no matter how many even numbers are in the subset. I will make the even and odd subsets separately to be $E={2, 4, 6, 8, 10, 12}$ and $O={1, 3, 5, 7, 9, 11}$. There are ${6choose1} + {6choose3} + {6choose5}=2^{5}=32$ ways to pick odd numbers. We can now pick as many evens as we wish, so we have $2^6$ ways to pick a subset. The union of the subset will just be the product of the two values, so we have $2^5 times 2^6=2^{11}=boxed{2048}$ subsets.

Thank you all so much for the help!

share|cite|improve this answer

answered 18 mins ago

A RA R

435

$endgroup$

add a comment | 

0

$begingroup$

The credit for this strategy goes entirely to JMoravitz.

What I didn't realize earlier is that as long as there are an odd number of odd numbers in our subset, then we can get an odd numbers, no matter how many even numbers are in the subset. I will make the even and odd subsets separately to be $E={2, 4, 6, 8, 10, 12}$ and $O={1, 3, 5, 7, 9, 11}$. There are ${6choose1} + {6choose3} + {6choose5}=2^{5}=32$ ways to pick odd numbers. We can now pick as many evens as we wish, so we have $2^6$ ways to pick a subset. The union of the subset will just be the product of the two values, so we have $2^5 times 2^6=2^{11}=boxed{2048}$ subsets.

Thank you all so much for the help!

share|cite|improve this answer

answered 18 mins ago

A RA R

435

$endgroup$

add a comment | 

$begingroup$

The credit for this strategy goes entirely to JMoravitz.

What I didn't realize earlier is that as long as there are an odd number of odd numbers in our subset, then we can get an odd numbers, no matter how many even numbers are in the subset. I will make the even and odd subsets separately to be $E={2, 4, 6, 8, 10, 12}$ and $O={1, 3, 5, 7, 9, 11}$. There are ${6choose1} + {6choose3} + {6choose5}=2^{5}=32$ ways to pick odd numbers. We can now pick as many evens as we wish, so we have $2^6$ ways to pick a subset. The union of the subset will just be the product of the two values, so we have $2^5 times 2^6=2^{11}=boxed{2048}$ subsets.

Thank you all so much for the help!

share|cite|improve this answer

answered 18 mins ago

A RA R

435

$endgroup$

share|cite|improve this answer

answered 18 mins ago

A RA R

435

answered 18 mins ago

A RA R

435

answered 18 mins ago

A RA R

435