5
$\begingroup$

We are given the set of numbers $T$ from $1$ to $2k$, in this case $k=1000$.

What is the smallest $n$, so that for $n$ selected numbers out of the set $T$ there definetly exists a number $a$ such that $a$ and $2a$ are both in the set?

Intuitively, the first thing I would have said is $k+1$ traditional pigeon-hole principle. It isn't hard to see that that is wrong- take all the odds and the numbers $4$ and $16$ for example. Grouping, we can combine numbers with their double and argue that only one in this group can be included in this grouping if we don't want to obtain doubles. Yet this grouping is not bijective, take for example the case $a=500$, which is grouped with $b=1000$, but $c=2000$ also is grouped with $b$, so it suffices to take out $b$. Knowing this, we could do an Inclusion-Exclusion Principle solution but it is quite time-consuming. Is there a more elegant solution?

$\endgroup$
12
  • $\begingroup$ Sorry, so $T=\{1,2,3,\dots, 2k\}$ and here $k=1000$ ? <s>Also how can $n=n+1$ (which is what you suggest) ??</s> On the other hand, $n\geq k+1$ is correct: You can always choose the numbers $a\in\{k+1,k+2,\dots, 2k\}$. $\endgroup$
    – Maximilian Janisch
    Commented Oct 15, 2020 at 18:27
  • $\begingroup$ I screwed up on my notation twice- I meant $n=k+1$ and $k=1000$. $\endgroup$
    – IMOPUTFIE
    Commented Oct 15, 2020 at 18:30
  • $\begingroup$ @MaximilianJanisch I am trying to find $n$ so that there always is a number $a$ and its double included in the chosen $n$ numbers, so yes, $n\geq k+1$. But I am looking for the smallest $n$ fulfilling this criterion i.e. the largest $n$ for which the criterion is not anymore fulfilled. $\endgroup$
    – IMOPUTFIE
    Commented Oct 15, 2020 at 18:32
  • $\begingroup$ @IMOPUTFIE Ah ok, also sorry but I can't figure out how to strike-through in comments. Nothing I have tried works :/ $\endgroup$
    – Maximilian Janisch
    Commented Oct 15, 2020 at 18:32
  • 1
    $\begingroup$ @MaximilianJanisch I have shown so in the second paragraph, yes $n>k+1$ is possible $\endgroup$
    – IMOPUTFIE
    Commented Oct 15, 2020 at 18:35

3 Answers 3

Reset to default
4
$\begingroup$

For numbers $1$ to $2k \, (= 2000)$, the minimum size $n$ of a random set that will ensure, there is at least one pair of $a, 2a$ present in the set -

Basically it works out to $n \displaystyle \ge 1 + \sum \limits_{i \ge 0} \lceil \frac{k}{2^{2i}}\rceil \, (2^{2i} \le 2k$, even powers of $2$). I think we can write a closed form but will be approximation.

Details -

Any or all of the odd numbers can be randomly present. So we need at least $k+1$ numbers.

So $ n \ge 1001$.

Now if we choose any number of the form $\, 2(2m-1)$ where $(m \ge 1, \in \mathbb{Z+})$ to be in the set, the set will have at least one pair of $(a, 2a)$.

But if the randomly chosen number to be in the set is of the form $4(2m-1)$ instead of $2(2m-1)$, then we still do not have a pair of $a,2a$.

Numbers of the form $4(2m-1) = 250 \,$ ($\lceil \frac{k}{4} \rceil)$.

So we are covered if the randomly chosen numbers are of the form $2(2m-1), 4(2m-1), 8(2m-1)$ but not covered for $4^2(2m-1)$.

Numbers of the form $4^2(2m-1) = 63 \,$ ($\lceil \frac{k}{4^2} \rceil)$.

Similarly, numbers of the form $4^3(2m-1) = 16 \,$ ($\lceil \frac{k}{4^3} \rceil)$.

numbers of the form $4^4(2m-1) = 4 \,$ ($\lceil \frac{k}{4^4} \rceil)$.

numbers of the form $4^5(2m-1) = 1\,$ ($\lceil \frac{k}{4^5} \rceil)$.

So, $n \ge 1001 + 250 + 63 + 16 + 4 + 1 = 1335$ will ensure there is at least a pair of numbers of the form $a,2a$.

$\endgroup$
4
  • $\begingroup$ For your general formula on top, should the $i$ not be bound by $2^{2i} \lt 2k$? why $\le$? $\endgroup$
    – Prags
    Commented Oct 15, 2020 at 22:19
  • $\begingroup$ In most cases that would not make a difference. But say, $2k$ is $1024 (2^10)$. $1024$ will not be chosen by any $4^i$ less than itself so if it is 2a, its a is not chosen. So we must account for it. $\endgroup$
    – Math Lover
    Commented Oct 15, 2020 at 22:35
  • $\begingroup$ You have shown that we have $n\geq 1335$, which is sweet, but you didn't show that the scenario you have assumed to be the worst case scenario is actually the worst case scenario... $\endgroup$
    – IMOPUTFIE
    Commented Oct 17, 2020 at 14:09
  • $\begingroup$ @IMOPUTFIE I think in my details, I showed that :) the process followed shows that $n = 1334$ would ensure all possible combinations of $a$ without $2a$ are covered. So, $+1$ would mean there is at least one pair of $a, 2a$. $\endgroup$
    – Math Lover
    Commented Oct 17, 2020 at 14:19
2
$\begingroup$

You can solve the problem via integer linear programming as follows. For $t\in T$, let binary decision variable $x_t$ indicate whether $t$ is selected. We want to maximize $\sum_t x_t$ subject to $x_t + x_{2t} \le 1$ for all $t\in\{1,\dots,k\}$. The maximum turns out to be $1334$, which means that $n=1334+1=1335$. One such optimal solution has $x_t=1$ for
$$t\in T\setminus\{2,6,8,10,14,18,22,24,26,30,32,34,38,40,42,46,50,54,56,58,62,66,70,72,74,78,82, 86,88,90,94,96,98,102,104,106,110,114,118,120,122,126,128,130,134,136,138,142,146,150,152,154, 158,160,162,166,168,170,174,178,182,184,186,190,194,198,200,202,206,210,214,216,218,222,224,226 ,230,232,234,238,242,246,248,250,254,258,262,264,266,270,274,278,280,282,286,288,290,294,296, 298,302,306,310,312,314,318,322,326,328,330,334,338,342,344,346,350,352,354,358,360,362,366,370 ,374,376,378,382,384,386,390,392,394,398,402,406,408,410,414,416,418,422,424,426,430,434,438, 440,442,446,450,454,456,458,462,466,470,472,474,478,480,482,486,488,490,494,498,501,502,503,504 ,505,506,507,509,510,511,512,513,514,515,517,518,519,520,521,522,523,525,526,527,529,530,531, 533,534,535,536,537,538,539,541,542,543,544,545,546,547,549,550,551,552,553,554,555,557,558,559 ,561,562,563,565,566,567,568,569,570,571,573,574,575,577,578,579,581,582,583,584,585,586,587, 589,590,591,593,594,595,597,598,599,600,601,602,603,605,606,607,608,609,610,611,613,614,615,616 ,617,618,619,621,622,623,625,626,627,629,630,631,632,633,634,635,637,638,639,640,641,642,643, 645,646,647,648,649,650,651,653,654,655,657,658,659,661,662,663,664,665,666,667,669,670,671,672 ,673,674,675,677,678,679,680,681,682,683,685,686,687,689,690,691,693,694,695,696,697,698,699, 701,702,703,705,706,707,709,710,711,712,713,714,715,717,718,719,721,722,723,725,726,727,728,729 ,730,731,733,734,735,736,737,738,739,741,742,743,744,745,746,747,749,750,751,753,754,755,757, 758,759,760,761,762,763,765,766,767,769,770,771,773,774,775,776,777,778,779,781,782,783,785,786 ,787,789,790,791,792,793,794,795,797,798,799,800,801,802,803,805,806,807,808,809,810,811,813, 814,815,817,818,819,821,822,823,824,825,826,827,829,830,831,833,834,835,837,838,839,840,841,842 ,843,845,846,847,849,850,851,853,854,855,856,857,858,859,861,862,863,864,865,866,867,869,870, 871,872,873,874,875,877,878,879,881,882,883,885,886,887,888,889,890,891,893,894,895,896,897,898 ,899,901,902,903,904,905,906,907,909,910,911,913,914,915,917,918,919,920,921,922,923,925,926, 927,928,929,930,931,933,934,935,936,937,938,939,941,942,943,945,946,947,949,950,951,952,953,954 ,955,957,958,959,961,962,963,965,966,967,968,969,970,971,973,974,975,977,978,979,981,982,983, 984,985,986,987,989,990,991,992,993,994,995,997,998,999,1000,1016,1032,1048,1056,1064,1080,1096 ,1112,1120,1128,1144,1152,1160,1176,1184,1192,1208,1224,1240,1248,1256,1272,1288,1304,1312,1320 ,1336,1352,1368,1376,1384,1400,1408,1416,1432,1440,1448,1464,1480,1496,1504,1512,1528,1536,1544 ,1560,1568,1576,1592,1608,1624,1632,1640,1656,1664,1672,1688,1696,1704,1720,1736,1752,1760,1768 ,1784,1800,1816,1824,1832,1848,1864,1880,1888,1896,1912,1920,1928,1944,1952,1960,1976,1992\}$$ The linear programming relaxation also has optimal objective value $1334$, and the dual variables provide a certificate of optimality in the form of $666$ disjoint pairs $(t,2t)$: $$P=\{(1,2),(3,6),(4,8),(5,10),(7,14),(9,18),(11,22),(12 ,24),(13,26),(15,30),(16,32),(17,34),(19,38),(20,40),(21,42),(23,46),(25,50),(27,54),(28,56),( 29,58),(31,62),(33,66),(35,70),(36,72),(37,74),(39,78),(41,82),(43,86),(44,88),(45,90),(47,94), (48,96),(49,98),(51,102),(52,104),(53,106),(55,110),(57,114),(59,118),(60,120),(61,122),(63,126 ),(64,128),(65,130),(67,134),(68,136),(71,142),(73,146),(75,150),(77,154),(79,158),(80,160),(85 ,170),(87,174),(91,182),(92,184),(93,186),(95,190),(99,198),(103,206),(105,210),(107,214),(108, 216),(111,222),(112,224),(113,226),(119,238),(127,254),(129,258),(131,262),(132,264),(133,266), (135,270),(137,274),(138,276),(139,278),(140,280),(141,282),(143,286),(144,288),(145,290),(147, 294),(148,296),(149,298),(151,302),(152,304),(153,306),(155,310),(156,312),(157,314),(159,318), (161,322),(162,324),(163,326),(164,328),(165,330),(166,332),(167,334),(168,336),(169,338),(171, 342),(172,344),(173,346),(175,350),(176,352),(177,354),(178,356),(179,358),(180,360),(181,362), (183,366),(185,370),(187,374),(188,376),(189,378),(191,382),(192,384),(193,386),(194,388),(195, 390),(196,392),(197,394),(199,398),(200,400),(201,402),(202,404),(203,406),(204,408),(205,410), (207,414),(208,416),(209,418),(211,422),(212,424),(213,426),(215,430),(217,434),(218,436),(219, 438),(220,440),(221,442),(223,446),(225,450),(227,454),(228,456),(229,458),(230,460),(231,462), (232,464),(233,466),(234,468),(235,470),(236,472),(237,474),(239,478),(240,480),(241,482),(242, 484),(243,486),(244,488),(245,490),(246,492),(247,494),(248,496),(249,498),(250,500),(251,502), (256,512),(260,520),(269,538),(272,544),(275,550),(283,566),(285,570),(287,574),(289,578),(292, 584),(297,594),(299,598),(301,602),(305,610),(307,614),(309,618),(311,622),(316,632),(317,634), (320,640),(321,642),(323,646),(329,658),(337,674),(339,678),(340,680),(341,682),(343,686),(345, 690),(348,696),(353,706),(363,726),(365,730),(367,734),(368,736),(369,738),(372,744),(373,746), (375,750),(377,754),(380,760),(381,762),(389,778),(391,782),(393,786),(395,790),(396,792),(401, 802),(405,810),(411,822),(412,824),(417,834),(425,850),(429,858),(431,862),(432,864),(433,866), (441,882),(444,888),(448,896),(449,898),(453,906),(455,910),(461,922),(463,926),(465,930),(469, 938),(471,942),(476,952),(477,954),(479,958),(481,962),(485,970),(495,990),(499,998),(501,1002) ,(503,1006),(504,1008),(505,1010),(506,1012),(507,1014),(508,1016),(509,1018),(510,1020),(511, 1022),(513,1026),(514,1028),(515,1030),(516,1032),(517,1034),(518,1036),(519,1038),(521,1042),( 522,1044),(523,1046),(524,1048),(525,1050),(526,1052),(527,1054),(528,1056),(529,1058),(530, 1060),(531,1062),(532,1064),(533,1066),(534,1068),(535,1070),(536,1072),(537,1074),(539,1078),( 540,1080),(541,1082),(542,1084),(543,1086),(545,1090),(546,1092),(547,1094),(548,1096),(549, 1098),(551,1102),(552,1104),(553,1106),(554,1108),(555,1110),(556,1112),(557,1114),(558,1116),( 559,1118),(560,1120),(561,1122),(562,1124),(563,1126),(564,1128),(565,1130),(567,1134),(568, 1136),(569,1138),(571,1142),(572,1144),(573,1146),(575,1150),(576,1152),(577,1154),(579,1158),( 580,1160),(581,1162),(582,1164),(583,1166),(585,1170),(586,1172),(587,1174),(588,1176),(589, 1178),(590,1180),(591,1182),(592,1184),(593,1186),(595,1190),(596,1192),(597,1194),(599,1198),( 600,1200),(601,1202),(603,1206),(604,1208),(605,1210),(606,1212),(607,1214),(608,1216),(609, 1218),(611,1222),(612,1224),(613,1226),(615,1230),(616,1232),(617,1234),(619,1238),(620,1240),( 621,1242),(623,1246),(624,1248),(625,1250),(626,1252),(627,1254),(628,1256),(629,1258),(630, 1260),(631,1262),(633,1266),(635,1270),(636,1272),(637,1274),(638,1276),(639,1278),(641,1282),( 643,1286),(644,1288),(645,1290),(647,1294),(648,1296),(649,1298),(650,1300),(651,1302),(652, 1304),(653,1306),(654,1308),(655,1310),(656,1312),(657,1314),(659,1318),(660,1320),(661,1322),( 662,1324),(663,1326),(664,1328),(665,1330),(666,1332),(667,1334),(668,1336),(669,1338),(670, 1340),(671,1342),(672,1344),(673,1346),(675,1350),(676,1352),(677,1354),(679,1358),(681,1362),( 683,1366),(684,1368),(685,1370),(687,1374),(688,1376),(689,1378),(691,1382),(692,1384),(693, 1386),(694,1388),(695,1390),(697,1394),(698,1396),(699,1398),(700,1400),(701,1402),(702,1404),( 703,1406),(704,1408),(705,1410),(707,1414),(708,1416),(709,1418),(710,1420),(711,1422),(712, 1424),(713,1426),(714,1428),(715,1430),(716,1432),(717,1434),(718,1436),(719,1438),(720,1440),( 721,1442),(722,1444),(723,1446),(724,1448),(725,1450),(727,1454),(728,1456),(729,1458),(731, 1462),(732,1464),(733,1466),(735,1470),(737,1474),(739,1478),(740,1480),(741,1482),(742,1484),( 743,1486),(745,1490),(747,1494),(748,1496),(749,1498),(751,1502),(752,1504),(753,1506),(755, 1510),(756,1512),(757,1514),(758,1516),(759,1518),(761,1522),(763,1526),(764,1528),(765,1530),( 766,1532),(767,1534),(768,1536),(769,1538),(770,1540),(771,1542),(772,1544),(773,1546),(774, 1548),(775,1550),(776,1552),(777,1554),(779,1558),(780,1560),(781,1562),(783,1566),(784,1568),( 785,1570),(787,1574),(788,1576),(789,1578),(791,1582),(793,1586),(794,1588),(795,1590),(796, 1592),(797,1594),(798,1596),(799,1598),(800,1600),(801,1602),(803,1606),(804,1608),(805,1610),( 806,1612),(807,1614),(808,1616),(809,1618),(811,1622),(812,1624),(813,1626),(814,1628),(815, 1630),(816,1632),(817,1634),(818,1636),(819,1638),(820,1640),(821,1642),(823,1646),(825,1650),( 826,1652),(827,1654),(828,1656),(829,1658),(830,1660),(831,1662),(832,1664),(833,1666),(835, 1670),(836,1672),(837,1674),(838,1676),(839,1678),(840,1680),(841,1682),(842,1684),(843,1686),( 844,1688),(845,1690),(846,1692),(847,1694),(848,1696),(849,1698),(851,1702),(852,1704),(853, 1706),(854,1708),(855,1710),(856,1712),(857,1714),(859,1718),(860,1720),(861,1722),(863,1726),( 865,1730),(867,1734),(868,1736),(869,1738),(870,1740),(871,1742),(872,1744),(873,1746),(874, 1748),(875,1750),(876,1752),(877,1754),(878,1756),(879,1758),(880,1760),(881,1762),(883,1766),( 884,1768),(885,1770),(886,1772),(887,1774),(889,1778),(890,1780),(891,1782),(892,1784),(893, 1786),(894,1788),(895,1790),(897,1794),(899,1798),(900,1800),(901,1802),(902,1804),(903,1806),( 904,1808),(905,1810),(907,1814),(908,1816),(909,1818),(911,1822),(912,1824),(913,1826),(914, 1828),(915,1830),(916,1832),(917,1834),(918,1836),(919,1838),(920,1840),(921,1842),(923,1846),( 924,1848),(925,1850),(927,1854),(928,1856),(929,1858),(931,1862),(932,1864),(933,1866),(934, 1868),(935,1870),(936,1872),(937,1874),(939,1878),(940,1880),(941,1882),(943,1886),(944,1888),( 945,1890),(946,1892),(947,1894),(948,1896),(949,1898),(950,1900),(951,1902),(953,1906),(955, 1910),(956,1912),(957,1914),(959,1918),(960,1920),(961,1922),(963,1926),(964,1928),(965,1930),( 966,1932),(967,1934),(968,1936),(969,1938),(971,1942),(972,1944),(973,1946),(974,1948),(975, 1950),(976,1952),(977,1954),(978,1956),(979,1958),(980,1960),(981,1962),(982,1964),(983,1966),( 984,1968),(985,1970),(986,1972),(987,1974),(988,1976),(989,1978),(991,1982),(992,1984),(993, 1986),(994,1988),(995,1990),(996,1992),(997,1994),(999,1998),(1000,2000) \}$$

Because at most one in each pair can be selected, this set $P$ of disjoint pairs proves that $$\sum_{t\in T} x_t \le |P| + (|T| - 2|P|) = |T| - |P| = 2000 - 666 = 1334.$$

$\endgroup$
1
$\begingroup$

This is not a full answer, but it should lead to a full answer with some more work I think.

Definition. A set $A\subset T$ is called admissible if there is no $a\in A$ such that $2a\in A$.

We note that the desired $n$ is given by $$n-1=\max\{|A|:A\subset T \text{ is admissible}\},$$ where $|A|$ is the cardinality of $A$.

Lemma. There is a set $B\subset T$ such that every odd number from one to $2k$ is in $B$ and such that $$|B|=\max\{|A|:A\subset T \text{ is admissible}\}.$$

Proof. Let $C$ be any set such that $|C|=\max\{|A|:A\subset T \text{ is admissible}\}$. Then form $B$ with the following process: For any odd number $a$ that is not in $C$, add $a$ to $C$ (and, if necessary, remove $2a$ from $C$). In short, $$B= (C\cup\{\text{odd numbers from $1$ to $2k$}\})\setminus\{2a : a \text{ is odd}\}.$$ Then $|B|\geq|C|$ so we are done. $\square$

Now we note that $B\setminus\{\text{odd numbers}\}$ cannot contain odd numbers, but it can't contain $2a$ for any odd number $a$ either.

So $B\setminus\{\text{odd numbers}\}\subset\{\text{numbers divisible by }4\}$.

So now the question is:

"Which numbers, that are divisible by $4$, can $B\setminus\{\text{odd numbers}\}$ contain?"

But that question really is equivalent to the original question, now with smaller size.

For example, for $k=1000$ after the above steps we need to look at $\{4,8,12,16,\dots,2000\}$, which is really the same as looking at $\{1,2,\dots, 500\}$. So we can reduce the problem from $k=1000$ to $k=250$. We can keep on reducing to $k=\lfloor\frac{250}4\rfloor=62$ and so on...

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .