farchielad
January 3rd, 2009, 10:08 AM
I have the following lema I need to proove in order to solve a certain algorithem:
Given two pairs of one dimensional arrays A and AA, B and BB . Each array is sorted and every member of A is smaller than its parallel in AA ( for example the parallel of a member in A is a member of AA located in the same position as that member in A), and every member of B is smaller than its parallel in BB.
AB is a sorted array containing all members of A and B.
AABB is a sorted array containing all members of AA and BB.
Prove that every member in AB is smaller than its parallel in AABB.
For example:
A=[1,6,10], B=[2,3,4], AA=[8,9,17], BB=[5,12,13].
AB=[1,2,3,4,6,10]
AABB=[5,8,9,12,13,17]
Thanks in advance
Elad
farchielad@gmail.com
Given two pairs of one dimensional arrays A and AA, B and BB . Each array is sorted and every member of A is smaller than its parallel in AA ( for example the parallel of a member in A is a member of AA located in the same position as that member in A), and every member of B is smaller than its parallel in BB.
AB is a sorted array containing all members of A and B.
AABB is a sorted array containing all members of AA and BB.
Prove that every member in AB is smaller than its parallel in AABB.
For example:
A=[1,6,10], B=[2,3,4], AA=[8,9,17], BB=[5,12,13].
AB=[1,2,3,4,6,10]
AABB=[5,8,9,12,13,17]
Thanks in advance
Elad
farchielad@gmail.com