A challenging Chinese college entrance examination adapted from 1988 Soviet Union Math competition. The new built-in DataStructrue features (HashTable and LinkedList) help to create very efficient implementation with compact code to simulate the proof with random inputs.

Problem

Given two lists of same finite length
m
,
{
a
n
}={
a
1
,
a
2
,
a
3
...,
a
m-1
,
a
m
}
and
{
b
n
}={
b
1
,
b
2
,
b
3
...,
b
m-1
,
b
m
}
. For each element
a
i
and
b
i
,
a
i
∈{1,2,3,...,m}
and
b
i
∈{1,2,3,...,m}
. Notice that the elements do NOT have to be distinct. Also define:​​
A
0
=
B
0
=0
,
A
n
=
a
1
+
a
2
+
a
3
+...+
a
n
​​
B
n
=
b
1
+
b
2
+
b
3
+...+
b
n
​
r
k
=max{i|
B
i
<=
A
k
}
with
i∈{0,1,2,...,m}
.​Show that there exist
1<=p<=q<=m
and
1<=s<=t<=m
s.t.
a
p
+
a
p+1
+
a
p+2
+...+
a
q
=
b
s
+
b
s+1
+
b
s+2
+...+
b
t
.

Simple example with m = 5

{
a
n
}={1,4,1,1,1}
and
{
b
n
}={3,4,3,2,4}
, therefore the
{
r
k
}={0,0,1,1,2,2}
(for zero based list). We find that
a
1
+
a
2
+
a
3
+
a
4
=1+4+1+1=
b
1
+
b
2
=3+4
. The task is to find such equal sum is always possible for list A and B satisfying the given condition. However, it is not feasible to enumerate all possibilities even for moderate sized input list due to enormous amount of valid candidates to test.

Simulation

The implementation is the word-by-word translation from the mathematical proof based on pigeonhole principle. Therefore it will always stop and return the earliest pair of subsequences with the same sum.

In[]:=
pigeonhole principle
Input interpretation
Dirichlet’s box principle
Alternate names
Dirichlet’s boxing-in principle
|
pigeonhole principle
Definition
A.k.a. the pigeonhole principle. Given
n
boxes and
m>n
objects, at least one box must contain more than one object. This statement has important applications in number theory and was first stated by Dirichlet in 1834.
In general, if
n
objects are placed into
k
boxes, then there exists at least one box containing at least
⌈n/k⌉
objects, where
⌈x⌉
is the ceiling function.
More information »
Related term
Fubini principle
Subject classifications
Show details
MathWorld
partitions
MSC 2010
05Axx
|
11Pxx
Associated person
Lejeune Dirichlet

Initialization

Using proper data structure greatly improves performance:
Clear[ht,lnklst]
ht=CreateDataStructure["HashTable"];​​lnklst=CreateDataStructure["LinkedList"];

Core of the algorithm

Set the length of the random input less than 300 so that we can have good visualization in the tabulated result.
In[]:=
m=256;
solAsso=Module{a,b,r,twoLists,count,pos,key},​​ht["KeyDropAll"];​​lnklst["DropAll"];​​(*randomlygenerateinputs.MakesureAm<Bm.Otherwisejustswitchtheorder*)​​twoLists=SortBy[RandomInteger[{1,m},{2,m}],Total];​​(*worstcaseonlyonedupe*)​​(*twoLists={ConstantArray[1,m],ConstantArray[m,m]};*)​​a=Accumulate[{0}~Join~(twoLists[[1]])];​​b=Accumulate[{0}~Join~(twoLists[[2]])];​​pos=Do​​r=
[◼]
BinarySearch
[b,a[[k]]];(*onlycomputenecessaryterms*)​​lnklst["Append",r];​​key=a[[k]]-b[[r]];​​If[!ht["KeyExistsQ",key],ht["Insert",key->k],Return[k]]​​,{k,1,m+1};​​<|"TwoLists"->twoLists,​​"RangeA"->{ht["Lookup",key],pos-1},​​"RangeB"->{lnklst["Part",ht["Lookup",key]],lnklst["Part",pos]-1}|>​​;
Here are some tips to understand the algorithm:
◼
  • Accumulate[{0}~Join~listA]
    is the
    A
    n
    in the problem.
    B
    n
    is similar.
    • ◼
  • a
    p
    +
    a
    p+1
    +
    a
    p+2
    +...+
    a
    q
    is expressed as
    A
    q
    -
    A
    p-1
    . Similar expression for
    b
    i
    ’s
    • ◼
  • The objects of pigeon-hole principle is
    A
    k
    -
    B
    r(k)
    with
    A
    k
    >=
    B
    r(k)
    and
    A
    k
    <
    B
    r(k)+1
    <=
    B
    r(k)
    +m
    . We can show that there are
    
    A
    0
    -
    B
    r(0)
    ,
    A
    1
    -
    B
    r(1)
    ,
    A
    2
    -
    B
    r(2)
    ,...,
    A
    m
    -
    B
    r(m)
    
    in total
    m+1
    objects and only
    m
    possible boxes with
    0<=
    A
    k
    -
    B
    r(k)
    <m
    . Therefore we must have at least one pair of duplication.
    • ◼
  • r
    k
    is computed incrementally with binary search of any
    A
    k
    in
    B
    list:
    r=
    [◼]
    BinarySearch
    [b,a[[k]]]
    • ◼
  • r
    k
    is stored in linked list data structure
    • ◼
  • Record each occurrence of new element and its location in a hash table;
    Terminate the loop if some element found again
    • ◼
  • Use the current value of iteration counter and hash table to extract the subsequences with same sum

    • Visualization

    The visualization code creates human-readable tabulated result and highlight which items are the earliest findings in each list with equal sum. The code is written to give you some flexibility to handle large inputs by dropping the unwanted parts:
    In[]:=
    Module{list1=solAsso["TwoLists"][[1]],list2=solAsso["TwoLists"][[2]],lb,ub,pre,suf},​​Scan[(list1[[#]]=Highlighted[list1[[#]]])&,Range@@solAsso["RangeA"]];​​Scan[(list2[[#]]=Highlighted[list2[[#]]])&,Range@@solAsso["RangeB"]];​​lb=Max[1,Min[solAsso["RangeA"][[1]]-2,solAsso["RangeB"][[1]]-2]];​​ub=Min[m,Max[solAsso["RangeA"][[2]]+2,solAsso["RangeB"][[2]]+2]];​​pre=If[lb==1,{},{"..."}];suf=If[ub==m,{},{"..."}];​​
    [◼]
    NiceGrid
    [{​​pre~Join~list1[[lb;;ub]]~Join~suf,​​pre~Join~list2[[lb;;ub]]~Join~suf,​​pre~Join~(Range[lb,ub])~Join~suf​​},{},{"List A","List B","Index"},Dividers->{False,{False,False,True}}]​​
    Out[]=
    Verify the sum of two subsequence are the same
    ◼
  • The subsequence highlighted in the first list
    • In[]:=
    Take[solAsso["TwoLists"][[1]],solAsso["RangeA"]]
    Out[]=
    {158,102,21,143,63,6,75,229,229}
    In[]:=
    Total[%]
    Out[]=
    1026
    ◼
  • The subsequence highlighted in the second list
    • In[]:=
    Take[solAsso["TwoLists"][[2]],solAsso["RangeB"]]
    Out[]=
    {84,154,142,112,11,243,77,203}
    In[]:=
    Total[%]
    Out[]=
    1026
    The corresponding hash table
    Partial list for
    R
    n
    :
    In[]:=
    lnklst["Visualization"]
    Out[]=
    Updated items in the hash table

    Construction of the worst case

    Release memory

    Summary

    ◼
  • Use hash table to store visited items in accumulated sum
    • ◼
  • Pay attention to the indices of zero based and 1 based array
    • ◼
  • The algorithm is probabilistically efficient for large input because the first pair of equal sum is very early even for really large input

    • Utility

    CITE THIS NOTEBOOK

    Find a pair of subsequences of equal sum from two lists​
    by Shenghui Yang​
    Wolfram Community, STAFF PICKS, June 22, 2023
    ​https://community.wolfram.com/groups/-/m/t/2940997