Choose signs such that $\pm\sqrt{1}\pm\sqrt{2}\pm\dots\pm\sqrt{2022}$ is as close as possible to $0$.

Question

Choose signs such that $\pm\sqrt{1}\pm\sqrt{2}\pm\dots\pm\sqrt{2022}$ is as close as possible to $0$.

I tried looking at examples for small $n$ (up to $8$) for inspiration:

$$\begin{align} &1: -\sqrt{1} = -1 &(0, 0) \\ &2: +\sqrt{1}-\sqrt{2} = -0.414214 &(10, 2) \\ &3: +\sqrt{1}+\sqrt{2}-\sqrt{3} = 0.682163 &(110, 6) \\ &4: -\sqrt{1}+\sqrt{2}+\sqrt{3}-\sqrt{4} = 0.146264 &(0110, 6) \\ &5: +\sqrt{1}+\sqrt{2}+\sqrt{3}-\sqrt{4}-\sqrt{5} = -0.0898034 &(11100, 28) \\ &6: -\sqrt{1}+\sqrt{2}+\sqrt{3}-\sqrt{4}+\sqrt{5}-\sqrt{6} = -0.0671574 &(011010, 26) \\ &7: -\sqrt{1}-\sqrt{2}-\sqrt{3}+\sqrt{4}+\sqrt{5}+\sqrt{6}-\sqrt{7} = -0.106458 &(0001110, 14) \\ &8: -\sqrt{1}+\sqrt{2}-\sqrt{3}+\sqrt{4}+\sqrt{5}+\sqrt{6}-\sqrt{7}-\sqrt{8} = -0.106458 &(01011100, 92) \end{align}$$

The right side $(x, y)$ is interpreted as $$ \begin{align} x &= \text{binary for + and - where + is 1 and - is 0} \\ y &= x \text{ to base 10} \\ \end{align} $$

Doing this, I had hoped for a pattern that emerges from say powers of two but nothing seems useful here.

By flipping each sign of a correct solution, we can trivially get another solution for each $n$. If it was integers, we could use the parity argument but I don't see a way forward for square roots.

This question was given in an interview for a trading firm. The interviewer wanted to hear how I would approach and analyze this problem under time-constrained circumstances. I asked this question in math.stackexchange because the structure of this question reminds me of typical Olympiad question where there's a "trick" to solving it.

Answer 1

You can solve the problem via integer linear programming as follows. For $j\in\{1,\dots,2022\}$, let binary decision variable $x_j$ indicate whether $\sqrt{j}$ appears with positive sign. The problem is to minimize $$ \left|\sum_j \sqrt{j} x_j - \sum_j \sqrt{j} (1-x_j)\right| =\left|\sum_j \sqrt{j} (2x_j-1)\right|, $$ which can be linearized by introducing a variable $z$ and minimizing $z$ subject to \begin{align} z &\ge \sum_j \sqrt{j} (2x_j-1) \\ z &\ge -\sum_j \sqrt{j} (2x_j-1) \\ \end{align}

The resulting optimal objective value turns out to be no more than 5.893526E-10:

{2,3,4,7,10,12,13,21,22,26,27,28,29,30,31,32,33,35,36,38,40,41,42,43,46,48,123,130,131,132,
134,135,137,138,139,143,144,146,147,150,152,155,158,159,166,168,169,170,180,184,186,196,199,234,
434,450,456,476,483,499,512,517,518,520,521,525,526,527,528,529,530,531,532,533,534,536,537,538,
539,540,541,546,547,548,550,553,554,557,558,560,570,571,572,578,580,581,583,584,588,591,592,594,
595,597,598,599,600,601,605,606,609,610,611,613,620,621,626,628,634,641,643,644,650,651,653,654,
655,658,662,665,669,670,672,676,684,685,688,691,692,695,698,700,703,710,712,719,721,722,723,731,
737,741,743,745,749,753,764,767,768,774,776,780,784,786,789,790,792,793,795,798,799,801,803,805,
810,828,850,854,859,860,861,871,872,874,880,881,890,1164,1274,1278,1279,1282,1283,1285,1286,1287,
1288,1290,1292,1294,1295,1297,1298,1299,1303,1304,1305,1306,1307,1308,1309,1311,1312,1313,1314,
1315,1316,1317,1318,1319,1320,1321,1322,1323,1325,1326,1328,1333,1334,1336,1340,1343,1346,1348,
1349,1350,1351,1352,1353,1354,1355,1356,1357,1359,1360,1361,1363,1364,1365,1366,1367,1369,1370,
1375,1377,1378,1379,1380,1381,1382,1383,1384,1387,1388,1390,1391,1392,1393,1394,1395,1396,1397,
1402,1406,1407,1410,1412,1414,1415,1416,1417,1418,1419,1420,1421,1422,1423,1424,1425,1427,1428,
1430,1432,1433,1435,1437,1438,1439,1440,1442,1443,1444,1445,1447,1448,1449,1450,1452,1453,1454,
1455,1458,1459,1460,1461,1462,1463,1464,1465,1467,1468,1470,1471,1472,1473,1474,1475,1478,1479,
1480,1481,1482,1483,1486,1487,1488,1489,1490,1491,1493,1495,1496,1497,1498,1499,1500,1501,1502,
1503,1505,1506,1507,1508,1509,1510,1511,1512,1513,1514,1517,1521,1523,1524,1525,1526,1527,1528,
1531,1532,1533,1534,1535,1536,1538,1539,1541,1542,1544,1545,1546,1548,1549,1550,1552,1553,1554,
1555,1557,1558,1559,1560,1562,1564,1565,1566,1567,1568,1569,1570,1571,1572,1573,1574,1575,1576,
1577,1578,1579,1581,1582,1583,1584,1585,1586,1587,1588,1589,1591,1592,1593,1594,1595,1596,1598,
1599,1600,1601,1602,1603,1604,1605,1606,1607,1608,1609,1610,1611,1612,1613,1614,1615,1616,1617,
1618,1619,1620,1621,1622,1623,1624,1625,1626,1627,1628,1629,1630,1631,1632,1633,1634,1635,1636,
1637,1638,1639,1640,1641,1642,1643,1644,1645,1646,1647,1649,1650,1651,1652,1653,1654,1655,1657,
1658,1659,1660,1661,1662,1663,1664,1665,1666,1667,1668,1669,1670,1672,1673,1674,1675,1676,1677,
1678,1679,1680,1681,1683,1684,1686,1687,1688,1689,1690,1691,1692,1693,1694,1695,1696,1697,1698,
1699,1700,1702,1703,1704,1705,1706,1707,1708,1709,1710,1711,1712,1713,1714,1715,1716,1717,1718,
1720,1721,1722,1723,1725,1726,1727,1728,1729,1730,1731,1732,1733,1734,1735,1736,1737,1738,1739,
1740,1741,1742,1743,1744,1747,1748,1749,1750,1752,1753,1754,1755,1756,1757,1758,1759,1760,1761,
1762,1763,1764,1765,1766,1767,1768,1769,1770,1771,1772,1774,1775,1776,1777,1778,1779,1780,1781,
1782,1783,1784,1785,1786,1787,1788,1789,1790,1791,1792,1793,1794,1795,1796,1797,1798,1799,1800,
1801,1802,1803,1804,1805,1806,1807,1808,1809,1810,1811,1813,1814,1815,1816,1817,1818,1819,1820,
1821,1822,1823,1824,1825,1826,1827,1828,1829,1830,1831,1832,1833,1834,1835,1836,1837,1838,1839,
1840,1841,1842,1843,1844,1845,1846,1847,1848,1849,1850,1851,1852,1853,1854,1855,1856,1857,1858,
1859,1860,1861,1862,1863,1864,1865,1866,1867,1868,1869,1870,1871,1872,1873,1874,1875,1876,1877,
1878,1879,1880,1881,1882,1883,1884,1885,1886,1887,1888,1889,1890,1891,1892,1893,1894,1895,1896,
1897,1898,1899,1900,1901,1902,1903,1904,1905,1906,1907,1908,1909,1910,1911,1912,1913,1914,1915,
1916,1917,1918,1919,1920,1921,1922,1923,1924,1925,1926,1927,1928,1929,1930,1931,1932,1933,1934,
1935,1936,1937,1938,1939,1940,1941,1942,1943,1944,1945,1946,1947,1948,1949,1950,1951,1952,1953,
1954,1955,1956,1957,1958,1959,1960,1961,1962,1963,1964,1965,1966,1967,1968,1969,1970,1971,1972,
1973,1974,1975,1976,1977,1978,1979,1980,1981,1982,1983,1985,1986,1987,1988,1989,1990,1991,1992,
1993,1994,1995,1996,1997,1998,1999,2000,2001,2002,2003,2004,2005,2006,2007,2008,2009,2010,2011,
2012,2013,2014,2015,2016,2017,2018,2019,2020,2021,2022}