Fdtxjr

Valid Badminton Score?

Are there any comparative studies done between Ashtavakra Gita and Buddhim?

Trouble understanding overseas colleagues

when is out of tune ok?

How can I get through very long and very dry, but also very useful technical documents when learning a new tool?

Understanding "audieritis" in Psalm 94

Applicability of Single Responsibility Principle

Hide Select Output from T-SQL

Why are on-board computers allowed to change controls without notifying the pilots?

Can I use my Chinese passport to enter China after I acquired another citizenship?

Is there any easy technique written in Bhagavad GITA to control lust?

Curses work by shouting - How to avoid collateral damage?

Where in the Bible does the greeting ("Dominus Vobiscum") used at Mass come from?

What is the opposite of 'gravitas'?

Short story about space worker geeks who zone out by 'listening' to radiation from stars

Why "be dealt cards" rather than "be dealing cards"?

Implement the Thanos sorting algorithm

What is the oldest known work of fiction?

Personal Teleportation as a Weapon

What defines a dissertation?

Everything Bob says is false. How does he get people to trust him?

How could Frankenstein get the parts for his _second_ creature?

How do I rename a LINUX host without needing to reboot for the rename to take effect?

Why did Kant, Hegel, and Adorno leave some words and phrases in the Greek alphabet?

Show that the distance between vectors is even

How to find number of different elements?Good set with $n$ elements must have element $ge 2over nbinomnnover2$?Equality of sums of sequencesCombining sets with a ruleIntersection of $left(A_icup B_iright)$ for two disjoint sets of eventsProve that the value of the expression $|a_1-b_1|+|a_2-b_2|+…+|a_n-b_n|$ does not depend on the coloring.Pigeonhole principle in finite sequenceProof there's a partition of set where for each $i$, $A_i cap B_i neq emptyset$Tuples with all coordinates summing to $3$find all the vectors such that the pairwise differences of whose entries are all different.

0

$begingroup$

Consider two vectors $(a_1, dots, a_n), (b_1, dots, b_n) in 0,1^n$ such that they both contain an even amount of ones. Is there an easy way to see that the set
$i: a_i neq b_i$ has even order? I.e., the two vectors are different in an even amount of positions.

I proved it by induction, but I'm looking for something simpler and more intuitive. Thanks.

combinatorics coding-theory

share|cite|improve this question

asked Mar 17 at 13:19

Math_QEDMath_QED

7,71131454

$endgroup$

add a comment | 

0

$begingroup$

Consider two vectors $(a_1, dots, a_n), (b_1, dots, b_n) in 0,1^n$ such that they both contain an even amount of ones. Is there an easy way to see that the set
$i: a_i neq b_i$ has even order? I.e., the two vectors are different in an even amount of positions.

I proved it by induction, but I'm looking for something simpler and more intuitive. Thanks.

combinatorics coding-theory

share|cite|improve this question

asked Mar 17 at 13:19

Math_QEDMath_QED

7,71131454

$endgroup$

add a comment | 

$begingroup$

Consider two vectors $(a_1, dots, a_n), (b_1, dots, b_n) in 0,1^n$ such that they both contain an even amount of ones. Is there an easy way to see that the set
$i: a_i neq b_i$ has even order? I.e., the two vectors are different in an even amount of positions.

I proved it by induction, but I'm looking for something simpler and more intuitive. Thanks.

combinatorics coding-theory

share|cite|improve this question

asked Mar 17 at 13:19

Math_QEDMath_QED

7,71131454

$endgroup$

share|cite|improve this question

asked Mar 17 at 13:19

Math_QEDMath_QED

7,71131454

share|cite|improve this question

asked Mar 17 at 13:19

Math_QEDMath_QED

7,71131454

asked Mar 17 at 13:19

Math_QEDMath_QED

7,71131454

asked Mar 17 at 13:19

Math_QEDMath_QED

7,71131454

3 Answers
3

active

oldest

votes

3

$begingroup$

$newcommand1mathbf1$One possibility: let $1$ denote the vector where each component is $1$. Note that a binary vector has an even number of $1$'s iff the sum of its elements is even (congruent to $0$ mod $2$). Thus $$1^T mathbfa equiv 0pmod2quadtextandquad 1^Tmathbfb equiv 0pmod2.$$ Hence $$1^T(mathbfa - mathbfb) equiv 0pmod2,$$ so the vector $mathbfa - mathbfbin0,1^n$ (using mod $2$ arithmetic) has an even number of $1$'s. This means that $mathbfa$ and $mathbfb$ differ in an even number of places. (You can show that $a_i - b_i equiv 1 pmod2$ iff $a_ine b_i$, for $a_i,b_iin0,1$.)

share|cite|improve this answer

edited Mar 17 at 13:38

answered Mar 17 at 13:33

Minus One-TwelfthMinus One-Twelfth

2,823413

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks. This answer was very clear!
  $endgroup$
  – Math_QED
  Mar 17 at 13:52
  

  
  
  
  

add a comment | 

2

$begingroup$

Let $A$ be the total number of $1$s between the two vectors, (i.e., $wt(veca) + wt(vecb)$), which is even since both vectors have an even number of ones. The positions where $veca$ and $vecb$ both have a $1$ consume an even number $B$ of $1$s (one in each vector). So the total number of $1$s in one vector where the other vector has a zero in the corresponding position is $A-B$, which is even. This is exactly the number of positions where the two vectors differ.

share|cite|improve this answer

answered Mar 17 at 13:38

Jeremy DoverJeremy Dover

1,259411

$endgroup$

add a comment | 

1

$begingroup$

Let $w(bf a)$ be the weight (number of ones) of the binary vector $bf a$

Then, operating in modulo 2, $bf c=bf a+bf b$ has ones in the positions where $bf a$,$bf b$ differ, zero otherwise. We are interested in the parity of $w(bf c)$.

But $w(bf a+bf b)=w(bf a)+w(bf b) -2 k$ where $k$ is the number of indexes where $a_i=b_i=1$.

Hence, if both $w(bf a)$,$w(bf b)$ are even, so is $w(bf c)$.

share|cite|improve this answer

answered Mar 21 at 19:47

leonbloyleonbloy

41.9k647108

$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%2f3151536%2fshow-that-the-distance-between-vectors-is-even%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

3

$begingroup$

$newcommand1mathbf1$One possibility: let $1$ denote the vector where each component is $1$. Note that a binary vector has an even number of $1$'s iff the sum of its elements is even (congruent to $0$ mod $2$). Thus $$1^T mathbfa equiv 0pmod2quadtextandquad 1^Tmathbfb equiv 0pmod2.$$ Hence $$1^T(mathbfa - mathbfb) equiv 0pmod2,$$ so the vector $mathbfa - mathbfbin0,1^n$ (using mod $2$ arithmetic) has an even number of $1$'s. This means that $mathbfa$ and $mathbfb$ differ in an even number of places. (You can show that $a_i - b_i equiv 1 pmod2$ iff $a_ine b_i$, for $a_i,b_iin0,1$.)

share|cite|improve this answer

edited Mar 17 at 13:38

answered Mar 17 at 13:33

Minus One-TwelfthMinus One-Twelfth

2,823413

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks. This answer was very clear!
  $endgroup$
  – Math_QED
  Mar 17 at 13:52
  

  
  
  
  

add a comment | 

3

$begingroup$

$newcommand1mathbf1$One possibility: let $1$ denote the vector where each component is $1$. Note that a binary vector has an even number of $1$'s iff the sum of its elements is even (congruent to $0$ mod $2$). Thus $$1^T mathbfa equiv 0pmod2quadtextandquad 1^Tmathbfb equiv 0pmod2.$$ Hence $$1^T(mathbfa - mathbfb) equiv 0pmod2,$$ so the vector $mathbfa - mathbfbin0,1^n$ (using mod $2$ arithmetic) has an even number of $1$'s. This means that $mathbfa$ and $mathbfb$ differ in an even number of places. (You can show that $a_i - b_i equiv 1 pmod2$ iff $a_ine b_i$, for $a_i,b_iin0,1$.)

share|cite|improve this answer

edited Mar 17 at 13:38

answered Mar 17 at 13:33

Minus One-TwelfthMinus One-Twelfth

2,823413

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks. This answer was very clear!
  $endgroup$
  – Math_QED
  Mar 17 at 13:52
  

  
  
  
  

add a comment | 

$begingroup$

$newcommand1mathbf1$One possibility: let $1$ denote the vector where each component is $1$. Note that a binary vector has an even number of $1$'s iff the sum of its elements is even (congruent to $0$ mod $2$). Thus $$1^T mathbfa equiv 0pmod2quadtextandquad 1^Tmathbfb equiv 0pmod2.$$ Hence $$1^T(mathbfa - mathbfb) equiv 0pmod2,$$ so the vector $mathbfa - mathbfbin0,1^n$ (using mod $2$ arithmetic) has an even number of $1$'s. This means that $mathbfa$ and $mathbfb$ differ in an even number of places. (You can show that $a_i - b_i equiv 1 pmod2$ iff $a_ine b_i$, for $a_i,b_iin0,1$.)

share|cite|improve this answer

edited Mar 17 at 13:38

answered Mar 17 at 13:33

Minus One-TwelfthMinus One-Twelfth

2,823413

$endgroup$

share|cite|improve this answer

edited Mar 17 at 13:38

answered Mar 17 at 13:33

Minus One-TwelfthMinus One-Twelfth

2,823413

answered Mar 17 at 13:33

Minus One-TwelfthMinus One-Twelfth

2,823413

answered Mar 17 at 13:33

Minus One-TwelfthMinus One-Twelfth

2,823413

2

$begingroup$

Let $A$ be the total number of $1$s between the two vectors, (i.e., $wt(veca) + wt(vecb)$), which is even since both vectors have an even number of ones. The positions where $veca$ and $vecb$ both have a $1$ consume an even number $B$ of $1$s (one in each vector). So the total number of $1$s in one vector where the other vector has a zero in the corresponding position is $A-B$, which is even. This is exactly the number of positions where the two vectors differ.

share|cite|improve this answer

answered Mar 17 at 13:38

Jeremy DoverJeremy Dover

1,259411

$endgroup$

add a comment | 

2

$begingroup$

Let $A$ be the total number of $1$s between the two vectors, (i.e., $wt(veca) + wt(vecb)$), which is even since both vectors have an even number of ones. The positions where $veca$ and $vecb$ both have a $1$ consume an even number $B$ of $1$s (one in each vector). So the total number of $1$s in one vector where the other vector has a zero in the corresponding position is $A-B$, which is even. This is exactly the number of positions where the two vectors differ.

share|cite|improve this answer

answered Mar 17 at 13:38

Jeremy DoverJeremy Dover

1,259411

$endgroup$

add a comment | 

$begingroup$

Let $A$ be the total number of $1$s between the two vectors, (i.e., $wt(veca) + wt(vecb)$), which is even since both vectors have an even number of ones. The positions where $veca$ and $vecb$ both have a $1$ consume an even number $B$ of $1$s (one in each vector). So the total number of $1$s in one vector where the other vector has a zero in the corresponding position is $A-B$, which is even. This is exactly the number of positions where the two vectors differ.

share|cite|improve this answer

answered Mar 17 at 13:38

Jeremy DoverJeremy Dover

1,259411

$endgroup$

share|cite|improve this answer

answered Mar 17 at 13:38

Jeremy DoverJeremy Dover

1,259411

answered Mar 17 at 13:38

Jeremy DoverJeremy Dover

1,259411

answered Mar 17 at 13:38

Jeremy DoverJeremy Dover

1,259411

1

$begingroup$

Let $w(bf a)$ be the weight (number of ones) of the binary vector $bf a$

Then, operating in modulo 2, $bf c=bf a+bf b$ has ones in the positions where $bf a$,$bf b$ differ, zero otherwise. We are interested in the parity of $w(bf c)$.

But $w(bf a+bf b)=w(bf a)+w(bf b) -2 k$ where $k$ is the number of indexes where $a_i=b_i=1$.

Hence, if both $w(bf a)$,$w(bf b)$ are even, so is $w(bf c)$.

share|cite|improve this answer

answered Mar 21 at 19:47

leonbloyleonbloy

41.9k647108

$endgroup$

add a comment | 

1

$begingroup$

Let $w(bf a)$ be the weight (number of ones) of the binary vector $bf a$

Then, operating in modulo 2, $bf c=bf a+bf b$ has ones in the positions where $bf a$,$bf b$ differ, zero otherwise. We are interested in the parity of $w(bf c)$.

But $w(bf a+bf b)=w(bf a)+w(bf b) -2 k$ where $k$ is the number of indexes where $a_i=b_i=1$.

Hence, if both $w(bf a)$,$w(bf b)$ are even, so is $w(bf c)$.

share|cite|improve this answer

answered Mar 21 at 19:47

leonbloyleonbloy

41.9k647108

$endgroup$

add a comment | 

$begingroup$

Let $w(bf a)$ be the weight (number of ones) of the binary vector $bf a$

Then, operating in modulo 2, $bf c=bf a+bf b$ has ones in the positions where $bf a$,$bf b$ differ, zero otherwise. We are interested in the parity of $w(bf c)$.

But $w(bf a+bf b)=w(bf a)+w(bf b) -2 k$ where $k$ is the number of indexes where $a_i=b_i=1$.

Hence, if both $w(bf a)$,$w(bf b)$ are even, so is $w(bf c)$.

share|cite|improve this answer

answered Mar 21 at 19:47

leonbloyleonbloy

41.9k647108

$endgroup$

share|cite|improve this answer

answered Mar 21 at 19:47

leonbloyleonbloy

41.9k647108

answered Mar 21 at 19:47

leonbloyleonbloy

41.9k647108

answered Mar 21 at 19:47

leonbloyleonbloy

41.9k647108