7
$\begingroup$

Find the least natural number $n$ such that if the set $\{1,2,\dots,n\}$ is arbitrarily divided into two non intersecting subsets then one of the subsets contains three distinct numbers such that the product of two of them equals the third.

Lets say I have two sets:

$A$ and $B$

So $1,2,3$ have to be in one set, lets put them in $A$. This forces $6$ to be in $B$ If we put $4$ in A, then $8,12$ must be in $B$. If we put $5$ in $A$ then $10,15$ must be in $B$. If we put $7$ in $A$ then $14,21$ to be in $B$.

So right now I have:

$$ A=\{1,2,3,4,5,7\} $$ $$ B=\{6,8,12,10,14,15,21\} $$

I don't see a particular pattern so i am assuming there is a different approach to this problem because this could go on forever. Any ideas?

EDIT: I misunderstood the question. Here is my new sets $$ A=\{1,2,3,6,9,12,24,36,72,18\} $$ $$ B=\{4,5,7,8,32,10,40,56,28,35,20\} $$

Here is my set so far

$\endgroup$
  • $\begingroup$ Can You explain what are $A$ and $B$? these are the subsets of $\{1\ldots n\}$? $\endgroup$ – CLAUDE Dec 15 '15 at 23:29
  • 1
    $\begingroup$ $1$ could be in either set, would it not matter? Why would $2,3$ have to be in the same set? $\endgroup$ – Mirko Dec 15 '15 at 23:32
  • 2
    $\begingroup$ then I think that you have understood the problem in a wrong manner, since it has said one of the sets contains (not for all triples) three distinct numbers such that ..., so the product of two of them must be in the same set, not in the other one, in addition it holds at least for one triple, not for all of them $\endgroup$ – CLAUDE Dec 15 '15 at 23:33
  • 1
    $\begingroup$ @Amir But if he finds the largest $n$ such that you can divide $\{1,\ldots,n\}$ into two sets no that there is no such triple in either set, then he will be almost finished (what the problem asks for will in that case just be $n+1$). $\endgroup$ – Arthur Dec 16 '15 at 0:05
  • 4
    $\begingroup$ The analogous problem for sums is much easier: an easy brute-force analysis shows that, if the set $\{1,\dots,9\}$ is partitioned into two classes, one class will contain two distinct numbers and their sum. Consequently, if the set $\{2^1,2^2,2^3,\dots,2^9\}$ is partitioned into two classes, one class will contain two distinct numbers and their product. Thus $2^9=512$ is an upper bound for the number you are looking for. $\endgroup$ – bof Dec 16 '15 at 0:19
4
$\begingroup$

The answer is $n=96$.
To prove this, take any $n\ge96$ and assume we partition the set $\{1,2,\cdots,n\}$ into the disjoint union of $A$ and $B$. Let $P(A)$ denote the set of products of distinct (and different from $1$) elements of $A$, similarly $P(B)$ denote the set of products of distinct (and different from $1$) elements of $B$.

Assume without loss of generality that $48\in B$ and consider cases as follows. Four cases are formed based on whether $2$ is in $A$ or in $B$, and whether $3$ is in $A$ or in $B$. In each case we assume that $A\cap P(A)=\emptyset$, $B\cap P(B)=\emptyset$, and derive a contradiction.

Case when $\{2,3\}\subseteq A$. Then $6\in B$ (since $6=2\cdot3$ and $\{2,3\}\subseteq A$). Then $8\in A$ (since $8=48/6$ and $\{6,48\}\subseteq B$), so $4=8/2\in B$. Then $24=3\cdot8=4\cdot6\in P(A)\cap P(B)$, which is enough to derive a contradiction. (Indeed, $24$ must be in either $A$ or $B$. In the former case the contradiction is that $24=3\cdot8\in A\cap P(A)$, in the latter case $24=4\cdot6\in B\cap P(B)$.)

It is perhaps easier to visualize the above argument as in the following table, where numbers further to the right are added to $A$ or $B$ as a consequence of numbers (at the left) that were added earlier.

$$ \begin{array}{l|c|c|c|c|r} \hline A & 2,\ {\color{red}3} & & {\color{red}8} & & {\color{red}{24}} &\\ \hline B & 48 & {\color{blue}6} & & {\color{blue}4} & {\color{blue}{24}} &\\ \hline \end{array} $$

Case when $2\in A$, $3\in B$. Then $16=48/3\in A$, $8=16/2\in B$, $\{6=48/8,\ 24=3\cdot8\}\subset A$, $\{4=24/6,\ 12=24/2,\ 48\}\subset B$, and $4\cdot12=48$. This case visualized as follows:
$$ \begin{array}{l|c|c|c|c|r} \hline A & 2 & 16 & & 6,\ 24 & &\\ \hline B & 3,\ {\color{blue}{48}} & & 8 & & {\color{blue}{4,\ 12}} &\\ \hline \end{array} $$

Case when $3\in A$, $2\in B$. Then $24=48/2\in A$, $8=24/3\in B$, $\{4=8/2,\ 6=48/8\}\subset A$, hence $4\cdot6=24$ with $\{4,6,24\}\subset A$. This case visualized as follows:
$$ \begin{array}{l|c|c|c|c|r} \hline A & 3 & {\color{red}{24}} & & {\color{red}{4,\ 6}} &\\ \hline B & 2,\ 48 & & 8 & & \\ \hline \end{array} $$

Finally, case $\{2,3\}\subseteq B$. Then $\{6=2\cdot3,\ 96=2\cdot48,\ 16=48/3\}\subset A$, a contradiction as $6\cdot16=96$. This last case visualized as follows:
$$ \begin{array}{l|c|c|c|c|r} \hline A & & {\color{red}{6,\ 96,\ 16}} & \\ \hline B & 2,\ 3,\ 48 & & \\ \hline \end{array} $$

It remains to show that we could partition the set $\{1,2,\cdots,95\}$ into the disjoint union $A\cup B$ such that no two distinct (and different from $1$) numbers in $A$ have a product in $A$, and no two distinct (and different from $1$) numbers in $B$ have a product in $B$.
That is, $A\cap P(A)=\emptyset$ and $B\cap P(B)=\emptyset$.

Using considerations as above, we start with $\{6,8,12,16,24,36,18\}\subset A$ and $\{2,3,4,48,72\}\subset B$, and add the remaining numbers up to $95$ one after the other in either $A$ or $B$ trying to avoid a conflict. This was done by hand (and after that checked with a computer).

The following partition works:

$A=\{6,8,10,12,14,15,16,18,20,21,22,24,26,27,28,30,32,33,34,35,36,38,39,40,42,44,45,46,50,51,52,55,57,58,62,63,65,68,69,74,75,76,77,78,82,85,86,87,91,92,93,94,95\}$

and

$B=\{1,2,3,4,5,7,9,11,13,17,19,23,25,29,31,37,41,43,47,48,49,53,54,56,59,60,61,64,66,67,70,71,72,73,79,80,81,83,84,88,89,90\}.$

To make the verification easier we also list $P(A)\cap\{1,2,\cdots,96\}$ and $P(B)\cap\{1,2,\cdots,96\}$.

$P(A)\cap\{1,2,\cdots,96\}=\{48,60,72,80,84,90,96\}.$

$P(B)\cap\{1,2,\cdots,96\}=\{6,8,10,12,14,15,18,20,21,22,26,27,28,33,34,35,36,38,39,44,45,46,50,51,52,55,57,58,62,63,65,68,69,74,75,76,77,82,85,86,87,91,92,93,94,95,96\}.$

Somewhat arbitrary $1$ and all primes ended up in $B$. This partition is not unique as $1$, $11$, and all primes $p\ge17$ (or any subset of these) could be moved from $B$ to $A$ without harm. (But $13$ could not be moved from $B$ to $A$ as this would create a conflict $6\cdot13=78$.) Many other variations are likely possible too.

One last edit to put $P(A)$, $A$, $B$, $P(B)$ all together for easier visual inspecion.

$$ \begin{array}{l|c|c|c|c|c|c|c|c|c|c|c|c|c|r} \hline P(A) & & & & & & & & & & & & & & & & & \\ \hline A & & & & & &6 & & 8& &10 & &12 & &14 &15 & 16& \\ \hline B &1 &2 &3 &4 &5 & &7 & &9 & &11 & &13 & & & & \\ \hline P(B) & & & & & &6 & &8 & &10 & &12 & &14 &15 & & \\ \hline \end{array} $$

$$ \begin{array}{l|c|c|c|c|c|c|c|c|c|c|c|c|c|r} \hline P(A) & & & & & & & & & & & & & & & & & \\ \hline A & &18 & &20 &21 &22 & &24 & &26 &27 &28 & &30 & &32 & \\ \hline B &17 & &19 & & & &23 & &25 & & & &29 & &31 & & \\ \hline P(B) & &18 & &20 &21 &22 & & & &26 &27 &28 & & & & & \\ \hline \end{array} $$

$$ \begin{array}{l|c|c|c|c|c|c|c|c|c|c|c|c|c|r} \hline P(A) & & & & & & & & & & & & & & & &48 & \\ \hline A &33 &34 &35 &36 & &38 &39 &40 & &42 & &44 &45 &46 & & & \\ \hline B & & & & &37 & & & &41 & &43 & & & &47 &48 & \\ \hline P(B) &33 &34 &35 &36 & &38 &39 & & & & &44 &45 &46 & & & \\ \hline \end{array} $$

$$ \begin{array}{l|c|c|c|c|c|c|c|c|c|c|c|c|c|r} \hline P(A) & & & & & & & & & & & &60 & & & & & \\ \hline A & &50 &51 &52 & & &55 & &57 &58 & & & &62 &63 & & \\ \hline B &49 & & & &53 &54 & &56 & & &59 &60 &61 & & &64 & \\ \hline P(B) & &50 &51 &52 & & &55 & &57 &58 & & & &62 &63 & & \\ \hline \end{array} $$

$$ \begin{array}{l|c|c|c|c|c|c|c|c|c|c|c|c|c|r} \hline P(A) & & & & & & & &72 & & & & & & & &80 & \\ \hline A &65 & & &68 &69 & & & & &74 &75 &76 &77 &78 & & & \\ \hline B & &66 &67 & & &70 &71 &72 &73 & & & & & &79 &80 & \\ \hline P(B) &65 & & &68 &69 & & & & &74 &75 &76 &77 & & & & \\ \hline \end{array} $$

$$ \begin{array}{l|c|c|c|c|c|c|c|c|c|c|c|c|c|r} \hline P(A) & & & &84 & & & & & &90 & & & & & &96 & \\ \hline A & &82 & & &85 &86 &87 & & & &91 &92 &93 &94 &95 & & \\ \hline B &81 & &83 &84 & & & &88 &89 &90 & & & & & & & \\ \hline P(B) & &82 & & &85 &86 &87 & & & &91 &92 &93 &94 &95 &96 & \\ \hline \end{array} $$

$\endgroup$
  • $\begingroup$ After posting my answer I found this AoPS link (which I also posted in a comment under the OP, along with a much longer link to a problem book on google books). The AoPS solution by seshadri gives the following partition of $\{1,2,\ldots,95\}$ one set $\{1,2,3,4,5,7,9\}\cup\{48,60,66,\dots,90,80,88\}$, the other $\{10,11,12,\dots,95\}\cup\{6,8\}\setminus\{60,66,\dots,90,80,88\}$. To see that $96$ works it considers cases depending on which of $2,4,8$ co-occur with $3$, two cases done in detail (indicating the remaining ones are similar). $\endgroup$ – Mirko Dec 16 '15 at 14:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.