Let a and b be two sorted arrays containing n integers each, in non-decreasing…
2005
Let a and b be two sorted arrays containing n integers each, in non-decreasing order. Let c be a sorted array containing 2n integers obtained by merging the two arrays a and b. Assuming the arrays are indexed starting from 0, consider the following four statements
a[i] ≥ b [i] => c[2i] ≥ a [i]
a[i] ≥ b [i] => c[2i] ≥ b [i]
a[i] ≥ b [i] => c[2i] ≤ a [i]
a[i] ≥ b [i] => c[2i] ≤ b [i]
Which of the following is TRUE?
- A.
only I and II
- B.
only I and IV
- C.
only II and III
- D.
only III and IV
Attempted by 79 students.
Show answer & explanation
Correct answer: C
Answer: only the statements "a[i] ≥ b[i] ⇒ c[2i] ≥ b[i]" and "a[i] ≥ b[i] ⇒ c[2i] ≤ a[i]" are true.
Proof that c[2i] ≥ b[i]: Assume for contradiction that c[2i] < b[i]. Then there are at least 2i+1 elements strictly less than b[i] in the merged array. In array b there are only i such elements (b[0..i-1]), so at least i+1 elements from array a must be < b[i]. Because a is sorted this implies a[i] < b[i], contradicting the hypothesis a[i] ≥ b[i]. Hence c[2i] ≥ b[i].
Proof that c[2i] ≤ a[i]: Assume for contradiction that c[2i] > a[i]. Then at most 2i elements are ≤ a[i] in the merged array. Array a itself contributes i+1 elements ≤ a[i] (a[0..i]), so array b would contribute at most i-1 such elements, which implies b[i] > a[i]. This contradicts a[i] ≥ b[i]. Therefore c[2i] ≤ a[i].
Counterexample showing the first statement is false: Take a = [10], b = [1], i = 0. Then a[0] ≥ b[0] but c[0] = 1 < a[0], so a[i] ≥ b[i] does not imply c[2i] ≥ a[i].
Counterexample showing the fourth statement is false: Take a = [5, 100], b = [1, 2], i = 1. Then a[1] = 100 ≥ b[1] = 2, but the merged array is [1,2,5,100] so c[2] = 5 > b[1], hence a[i] ≥ b[i] does not imply c[2i] ≤ b[i].