I've been trying to prove the following, without much success.(adsbygoogle = window.adsbygoogle || []).push({});

Let ##B## and ##C## be nonempty finite subsets of an ordered field ##\mathbb{F}##. Define the swapping operation ##S## as follows:

It takes an element ##b## from ##B##, an element ##c## from ##C##, removes ##b## from ##B## and gives it to ##C##, removes ##c## from ##C## and gives it to ##B##.

Now suppose that ##\max(B) \geq \min(C)##. Then prove that in a finite number of operations of S, the sets ##B## and ##C## can be transformed so that ##\max(B) < \min(C)##.

Where would I start? I'm thinking by we can use induction/loop invariants, but I don't have much experience in algorithm proofs, so I could use some help. Thanks!

BiP

**Physics Forums - The Fusion of Science and Community**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Proving termination and correctness of the algorithm

Loading...

Similar Threads - Proving termination correctness | Date |
---|---|

I Prove if x + (1/x) = 1 then x^7 + (1/x^7) = 1. | Mar 9, 2016 |

I Proving Odd and Even | Feb 13, 2016 |

Prove A.(B+C) = (A.B)+(A.C) <Boolean Algebra> | Oct 24, 2015 |

Expected number of games in a series that terminates | Oct 31, 2011 |

**Physics Forums - The Fusion of Science and Community**