Prove that for any three distinct positive integers, at least one will be greater than the xor of the other [closed]Gradualness of Polynomial-time RecognizersHow to reverse this bitwise AND-XOR encoding algorithm?Strange behavior with xor, and, or bit operations on integer offsetsProving Gale-Shapley algorithm completes in $O(n^2)$Goldbach Conjecture and the Busy Beaver function?Time constructible function in Hierarchy TheoremHow to prove/make sure that the answer to this question will be m^1/2Mathematics for Computer Science, Problem 2.6. WOPShowing an Inequality Holds TrueProof lower bound of $lceiln/2rceil$ comparisons for finding smallest and second smallest element
Loading the leaflet Map in Lightning Web Component
gerund and noun applications
What exactly term 'companion plants' means?
What is the relationship between relativity and the Doppler effect?
Generic TVP tradeoffs?
Am I eligible for the Eurail Youth pass? I am 27.5 years old
What favor did Moody owe Dumbledore?
Describing a chess game in a novel
What (if any) is the reason to buy in small local stores?
Can a medieval gyroplane be built?
What is the term when voters “dishonestly” choose something that they do not want to choose?
How do hiring committees for research positions view getting "scooped"?
Suggestions on how to spend Shaabath (constructively) alone
How can an organ that provides biological immortality be unable to regenerate?
Optimising a list searching algorithm
What does Jesus mean regarding "Raca," and "you fool?" - is he contrasting them?
Print a physical multiplication table
Can other pieces capture a threatening piece and prevent a checkmate?
Can a wizard cast a spell during their first turn of combat if they initiated combat by releasing a readied spell?
Pronounciation of the combination "st" in spanish accents
World War I as a war of liberals against authoritarians?
Are dual Irish/British citizens bound by the 90/180 day rule when travelling in the EU after Brexit?
Using Past-Perfect interchangeably with the Past Continuous
PTIJ What is the inyan of the Konami code in Uncle Moishy's song?
Prove that for any three distinct positive integers, at least one will be greater than the xor of the other [closed]
Gradualness of Polynomial-time RecognizersHow to reverse this bitwise AND-XOR encoding algorithm?Strange behavior with xor, and, or bit operations on integer offsetsProving Gale-Shapley algorithm completes in $O(n^2)$Goldbach Conjecture and the Busy Beaver function?Time constructible function in Hierarchy TheoremHow to prove/make sure that the answer to this question will be m^1/2Mathematics for Computer Science, Problem 2.6. WOPShowing an Inequality Holds TrueProof lower bound of $lceiln/2rceil$ comparisons for finding smallest and second smallest element
$begingroup$
That is, prove that for distinct positive integers $x$, $y$, and $z$, at least one of these integers will be greater than the bitwise XOR of the other two integers.
The only "progress" I managed to make was assuming for the sake of contradiction that we could have $x<y$ XOR $z$ and so on. Then, this would imply $x+y+z<x$ XOR $y+y$ XOR $z+z$ XOR $x$. I tried proving this was impossible but later found a counterexample :(
computer-science bit-strings
asked Mar 12 at 20:46
J. TymeJ. Tyme
11
New contributor
J. Tyme is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
closed as off-topic by John Omielan, Eevee Trainer, Lee David Chung Lin, Shailesh, hardmath Mar 13 at 0:48
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – John Omielan, Eevee Trainer, Lee David Chung Lin, Shailesh, hardmath
add a comment |
$begingroup$
That is, prove that for distinct positive integers $x$, $y$, and $z$, at least one of these integers will be greater than the bitwise XOR of the other two integers.
The only "progress" I managed to make was assuming for the sake of contradiction that we could have $x<y$ XOR $z$ and so on. Then, this would imply $x+y+z<x$ XOR $y+y$ XOR $z+z$ XOR $x$. I tried proving this was impossible but later found a counterexample :(
computer-science bit-strings
asked Mar 12 at 20:46
J. TymeJ. Tyme
11
New contributor
J. Tyme is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
closed as off-topic by John Omielan, Eevee Trainer, Lee David Chung Lin, Shailesh, hardmath Mar 13 at 0:48
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – John Omielan, Eevee Trainer, Lee David Chung Lin, Shailesh, hardmath
2
$begingroup$
Welcome to MSE. Please give some context, in particular, tell us what you've tried so far, including anything in particular you had difficulty with. Also, letting us know where this problem comes from would be helpful. Thanks.
$endgroup$
– John Omielan
Mar 12 at 20:47
1
$begingroup$
The "bare problem statement" is disfavored, not only because it typically conveys an imperative, but also because it fails to disclose what you find interesting or difficult about the problem. Showing that you digested the problem's meaning before posting will often encourage Readers to provide the best exposition they can.
$endgroup$
– hardmath
Mar 13 at 0:47
add a comment |
$begingroup$
That is, prove that for distinct positive integers $x$, $y$, and $z$, at least one of these integers will be greater than the bitwise XOR of the other two integers.
The only "progress" I managed to make was assuming for the sake of contradiction that we could have $x<y$ XOR $z$ and so on. Then, this would imply $x+y+z<x$ XOR $y+y$ XOR $z+z$ XOR $x$. I tried proving this was impossible but later found a counterexample :(
computer-science bit-strings
asked Mar 12 at 20:46
J. TymeJ. Tyme
11
New contributor
J. Tyme is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
That is, prove that for distinct positive integers $x$, $y$, and $z$, at least one of these integers will be greater than the bitwise XOR of the other two integers.
The only "progress" I managed to make was assuming for the sake of contradiction that we could have $x<y$ XOR $z$ and so on. Then, this would imply $x+y+z<x$ XOR $y+y$ XOR $z+z$ XOR $x$. I tried proving this was impossible but later found a counterexample :(
computer-science bit-strings
computer-science bit-strings
asked Mar 12 at 20:46
J. TymeJ. Tyme
11
New contributor
J. Tyme is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Mar 12 at 20:46
J. TymeJ. Tyme
11
New contributor
J. Tyme is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited Mar 13 at 1:18
J. Tyme
asked Mar 12 at 20:46
J. TymeJ. Tyme
11
New contributor
J. Tyme is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Mar 12 at 20:46
J. TymeJ. Tyme
11
asked Mar 12 at 20:46
J. TymeJ. Tyme
11
11
New contributor
J. Tyme is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
J. Tyme is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
J. Tyme is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
closed as off-topic by John Omielan, Eevee Trainer, Lee David Chung Lin, Shailesh, hardmath Mar 13 at 0:48
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – John Omielan, Eevee Trainer, Lee David Chung Lin, Shailesh, hardmath
closed as off-topic by John Omielan, Eevee Trainer, Lee David Chung Lin, Shailesh, hardmath Mar 13 at 0:48
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – John Omielan, Eevee Trainer, Lee David Chung Lin, Shailesh, hardmath
2
$begingroup$
Welcome to MSE. Please give some context, in particular, tell us what you've tried so far, including anything in particular you had difficulty with. Also, letting us know where this problem comes from would be helpful. Thanks.
$endgroup$
– John Omielan
Mar 12 at 20:47
1
$begingroup$
The "bare problem statement" is disfavored, not only because it typically conveys an imperative, but also because it fails to disclose what you find interesting or difficult about the problem. Showing that you digested the problem's meaning before posting will often encourage Readers to provide the best exposition they can.
$endgroup$
– hardmath
Mar 13 at 0:47
add a comment |
2
$begingroup$
Welcome to MSE. Please give some context, in particular, tell us what you've tried so far, including anything in particular you had difficulty with. Also, letting us know where this problem comes from would be helpful. Thanks.
$endgroup$
– John Omielan
Mar 12 at 20:47
1
$begingroup$
The "bare problem statement" is disfavored, not only because it typically conveys an imperative, but also because it fails to disclose what you find interesting or difficult about the problem. Showing that you digested the problem's meaning before posting will often encourage Readers to provide the best exposition they can.
$endgroup$
– hardmath
Mar 13 at 0:47
2
2
$begingroup$
Welcome to MSE. Please give some context, in particular, tell us what you've tried so far, including anything in particular you had difficulty with. Also, letting us know where this problem comes from would be helpful. Thanks.
$endgroup$
– John Omielan
Mar 12 at 20:47
$begingroup$
Welcome to MSE. Please give some context, in particular, tell us what you've tried so far, including anything in particular you had difficulty with. Also, letting us know where this problem comes from would be helpful. Thanks.
$endgroup$
– John Omielan
Mar 12 at 20:47
1
1
$begingroup$
The "bare problem statement" is disfavored, not only because it typically conveys an imperative, but also because it fails to disclose what you find interesting or difficult about the problem. Showing that you digested the problem's meaning before posting will often encourage Readers to provide the best exposition they can.
$endgroup$
– hardmath
Mar 13 at 0:47
$begingroup$
The "bare problem statement" is disfavored, not only because it typically conveys an imperative, but also because it fails to disclose what you find interesting or difficult about the problem. Showing that you digested the problem's meaning before posting will often encourage Readers to provide the best exposition they can.
$endgroup$
– hardmath
Mar 13 at 0:47
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
So let's write $x$, $y$ and $z$ as binary numbers where the first digit is a $1$ (note that the numbers are strictly positive). Some hints:
- If one number has more digits than the other two, what can we do? Can XOR ever return a number with more digits than its two inputs?
- How can we extend this to the case where two numbers have the same number of digits as each other, and this is more than the number of digits of the third number?
- If each number has the same number of digits, they all start with a $1$. What happens if you take the bitwise XOR of any two of the numbers?
answered Mar 12 at 21:14
AdamAdam
748113
$endgroup$
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
So let's write $x$, $y$ and $z$ as binary numbers where the first digit is a $1$ (note that the numbers are strictly positive). Some hints:
- If one number has more digits than the other two, what can we do? Can XOR ever return a number with more digits than its two inputs?
- How can we extend this to the case where two numbers have the same number of digits as each other, and this is more than the number of digits of the third number?
- If each number has the same number of digits, they all start with a $1$. What happens if you take the bitwise XOR of any two of the numbers?
answered Mar 12 at 21:14
AdamAdam
748113
$endgroup$
add a comment |
$begingroup$
So let's write $x$, $y$ and $z$ as binary numbers where the first digit is a $1$ (note that the numbers are strictly positive). Some hints:
- If one number has more digits than the other two, what can we do? Can XOR ever return a number with more digits than its two inputs?
- How can we extend this to the case where two numbers have the same number of digits as each other, and this is more than the number of digits of the third number?
- If each number has the same number of digits, they all start with a $1$. What happens if you take the bitwise XOR of any two of the numbers?
answered Mar 12 at 21:14
AdamAdam
748113
$endgroup$
add a comment |
$begingroup$
So let's write $x$, $y$ and $z$ as binary numbers where the first digit is a $1$ (note that the numbers are strictly positive). Some hints:
- If one number has more digits than the other two, what can we do? Can XOR ever return a number with more digits than its two inputs?
- How can we extend this to the case where two numbers have the same number of digits as each other, and this is more than the number of digits of the third number?
- If each number has the same number of digits, they all start with a $1$. What happens if you take the bitwise XOR of any two of the numbers?
answered Mar 12 at 21:14
AdamAdam
748113
$endgroup$
So let's write $x$, $y$ and $z$ as binary numbers where the first digit is a $1$ (note that the numbers are strictly positive). Some hints:
- If one number has more digits than the other two, what can we do? Can XOR ever return a number with more digits than its two inputs?
- How can we extend this to the case where two numbers have the same number of digits as each other, and this is more than the number of digits of the third number?
- If each number has the same number of digits, they all start with a $1$. What happens if you take the bitwise XOR of any two of the numbers?
answered Mar 12 at 21:14
AdamAdam
748113
answered Mar 12 at 21:14
AdamAdam
748113
answered Mar 12 at 21:14
AdamAdam
748113
answered Mar 12 at 21:14
AdamAdam
748113
748113
add a comment |
add a comment |
2
$begingroup$
Welcome to MSE. Please give some context, in particular, tell us what you've tried so far, including anything in particular you had difficulty with. Also, letting us know where this problem comes from would be helpful. Thanks.
$endgroup$
– John Omielan
Mar 12 at 20:47
1
$begingroup$
The "bare problem statement" is disfavored, not only because it typically conveys an imperative, but also because it fails to disclose what you find interesting or difficult about the problem. Showing that you digested the problem's meaning before posting will often encourage Readers to provide the best exposition they can.
$endgroup$
– hardmath
Mar 13 at 0:47