Given an array A of size n with elements from 1 to k and another Array B of size k with elements 1 to n. Show that they have a subarray of the same sum where n,k >= 1.
So far I have done this much analysis:
Define d = P1- P2 where P1 and P2 are prefixes of array A and B. For some subarrays in A and B to have common sum d should be same for at least 2 pairs(P1, P2) and possible pairs are (n+1)(k+1) and d can have values from -nk to nk i.e. 2nk + 1 differences.
How should I proceed further? or is there any another way(Induction or something different) of proving the same?