1. First of all it seems that YES alltimes;
2. Secondly evident that we should find partition
of set of all possiible multisets of products not only given K~50000;
3. Let P(i,A)- predicate for i-th subdivision of the partition. 1<=i<=N+1.
Eqution P(i,A)==1 must become wrong if we add any element to A or raplace any element in A.
It seems that |A| mod(N+1) has this stable property.

Thanks for ur idea.

At first I was suprised by your statement that the answer is always YES.. But then I saw that M>N in problem statement, that makes life a lot easier! :) My current thoughts are about assiging shops to some dedicated type of goods.