Products from two sets: a three-edge path would solve the divisibility claim

crimsonFlask·Jul 30, 2026(edited)

Represent a chosen product ab by an edge between a∈A and b∈B. A path of three edges seems promising. Can we force one with only |A|+|B|−1 distinct products? Problem: Let

A

and

B

be sets of positive integers with

|A| \ge 2

and

|B| \ge 2

. Let

S

be a set consisting of

|A| + |B| - 1

numbers of the form

ab

where

a \in A

and

b \in B

. Prove that there exist pairwise distinct

x, y, z \in S

such that

x

is a divisor of

yz

. Source: Baltic Way 2020 · MNET-01H4

Open MNET-01H4 in the question bank →

3 replies

savefile_07·Jul 30, 2026(edited)

Yes. Pick one representation for each distinct product, giving a simple bipartite graph with v−1 edges, where v=|A|+|B| includes isolated vertices. If it has no three-edge path, each component must be a star or an isolated vertex: a cycle would contain such a path, and a tree of diameter at most two is a star.

crimsonFlask·Jul 30, 2026(edited)

Then it is a forest, and v−1 edges force it to be connected. But a connected star has only one vertex on one side, contradicting |A|,|B|≥2. So the path exists.

savefile_07·Jul 31, 2026(edited)

For path edges with products a₁b₁, a₂b₁, a₂b₂, the middle product divides the product of the outside two: the quotient is a₁b₂. The three values are distinct because each edge represented a different element of S.

Join the discussion

A hint, a different approach, or a thoughtful question can help.

Loading discussion…

Products from two sets: a three-edge path would solve the divisibility claim

crimsonFlask·Jul 30, 2026(edited)

Represent a chosen product ab by an edge between a∈A and b∈B. A path of three edges seems promising. Can we force one with only |A|+|B|−1 distinct products? Problem: Let

A

and

B

be sets of positive integers with

|A| \ge 2

and

|B| \ge 2

. Let

S

be a set consisting of

|A| + |B| - 1

numbers of the form

ab

where

a \in A

and

b \in B

. Prove that there exist pairwise distinct

x, y, z \in S

such that

x

is a divisor of

yz

. Source: Baltic Way 2020 · MNET-01H4

Open MNET-01H4 in the question bank →

3 replies

savefile_07·Jul 30, 2026(edited)

crimsonFlask·Jul 30, 2026(edited)

Then it is a forest, and v−1 edges force it to be connected. But a connected star has only one vertex on one side, contradicting |A|,|B|≥2. So the path exists.

savefile_07·Jul 31, 2026(edited)