29
$\begingroup$

The numbers $ 2, \ldots, 2015 $ are written on a blackboard. Each minute any two numbers $ x $ and $ y $ are wiped out and are replaced by two numbers $\displaystyle \frac { 4x + 3y } { 5 } $ and $\displaystyle \frac { 24x - 7y } { 25 } $.

Is it possible that after some time the numbers $ 1, \ldots, 2014 $ are written on the blackboard ?

$\endgroup$
10
  • 11
    $\begingroup$ I assume that $(3,4,5)$ and $(7,24,25)$ being Pythagorean triples has something to do with the solution... $\endgroup$ Oct 15, 2015 at 19:26
  • 11
    $\begingroup$ Also possibly relevant: $(\frac{4i+3}{5})^2=\frac{24i-7}{25}$ $\endgroup$
    – f''
    Oct 15, 2015 at 23:18
  • 11
    $\begingroup$ Are we assuming all the numbers are integers? Do fractions get written up, or are they rounded? $\endgroup$ Oct 16, 2015 at 13:23
  • 3
    $\begingroup$ $14(\frac{4x+3y}{5})^2+25(\frac{24x-7y}{25})^2=32x^2+7y^2$ $\endgroup$
    – f''
    Oct 16, 2015 at 17:26
  • 4
    $\begingroup$ @Haobin Do you know the answer? $\endgroup$ Oct 25, 2015 at 15:43

2 Answers 2

14
+150
$\begingroup$

Answer

Yes it is possible.

The (maybe) interesting details

I started by creating a huge HTML table containing an overview of the generated values (right click the image and select "View image" for bigger version):

table

I ignored non integer values, therefore most of the fields are empty. The integer values form a regular pattern. The highlighted fields are the ones which keep one of the values unchanged. In addition to the 3 variants mentioned by GentlePurpleRain above, there is one more which uses negative values.

Using a highlighted red field it's possible to increase a single value while keeping the other unchanged. Using a highlighted blue field allows to decrease a single value. However, this is not enough to solve the puzzle. The next step was to increase the complexity. Look at the field representing [6, 17] -> [15, 1]. This changes two values, but we can restore one of them in a second step, namely [15 30] -> [30 6]. The effect of both these replacements is [17] -> [1].

There are more possibilities, e.g. [255, 510] -> [510, 102] and [102, 289] -> [255, 17] result in [289] -> [17]. Together with the previous combination we have [289] -> [1].

This can be continued further, which I have done using a computer program. It starts with the highlighted fields, and in each iteration adds more possible single number transformations to the list, until it finds the transformation [2015] -> [1]. See next chapter for the result.

The ugly details

Here is a possible sequence. It's not necessarily the shortest one, it's the one which was easiest to find.

Replacement Surplus Missing
. [2015] [1]
[300, 100] -> [300, 260] [260, 2015] [1, 100]
[180, 260] -> [300, 100] [300, 2015] [1, 180]
[300, 600] -> [600, 120] [120, 2015] [1, 180]
[135, 120] -> [180, 96] [96, 2015] [1, 135]
[96, 97] -> [135, 65] [65, 2015] [1, 97]
[120, 65] -> [135, 97] [135, 2015] [1, 120]
[96, 72] -> [120, 72] [135, 2015] [1, 96]
[135, 120] -> [180, 96] [180, 2015] [1, 120]
[252, 189] -> [315, 189] [180, 315, 2015] [1, 120, 252]
[315, 180] -> [360, 252] [360, 2015] [1, 120]
[360, 720] -> [720, 144] [144, 2015] [1, 120]
[167, 144] -> [220, 120] [220, 2015] [1, 167]
[308, 231] -> [385, 231] [220, 385, 2015] [1, 167, 308]
[385, 220] -> [440, 308] [440, 2015] [1, 167]
[440, 880] -> [880, 176] [176, 2015] [1, 167]
[176, 7] -> [145, 167] [145, 2015] [1, 7]
[375, 750] -> [750, 150] [145, 150, 2015] [1, 7, 375]
[150, 425] -> [375, 25] [25, 145, 2015] [1, 7, 425]
[450, 25] -> [375, 425] [145, 375, 2015] [1, 7, 450]
[375, 250] -> [450, 290] [145, 290, 2015] [1, 7, 250]
[290, 30] -> [250, 270] [145, 270, 2015] [1, 7, 30]
[225, 450] -> [450, 90] [90, 145, 270, 2015] [1, 7, 30, 225]
[90, 255] -> [225, 15] [15, 145, 270, 2015] [1, 7, 30, 255]
[270, 15] -> [225, 255] [145, 225, 2015] [1, 7, 30]
[225, 450] -> [450, 90] [90, 145, 2015] [1, 7, 30]
[270, 90] -> [270, 234] [145, 234, 2015] [1, 7, 30]
[390, 130] -> [390, 338] [145, 234, 338, 2015] [1, 7, 30, 130]
[234, 338] -> [390, 130] [145, 390, 2015] [1, 7, 30]
[145, 390] -> [350, 30] [350, 2015] [1, 7]
[315, 105] -> [315, 273] [273, 350, 2015] [1, 7, 105]
[189, 273] -> [315, 105] [315, 350, 2015] [1, 7, 189]
[224, 168] -> [280, 168] [280, 315, 350, 2015] [1, 7, 189, 224]
[315, 280] -> [420, 224] [350, 420, 2015] [1, 7, 189]
[420, 315] -> [525, 315] [350, 525, 2015] [1, 7, 189]
[350, 525] -> [595, 189] [595, 2015] [1, 7]
[595, 2015] -> [1685, 7] [1685] [1]
[60, 20] -> [60, 52] [52, 1685] [1, 20]
[36, 52] -> [60, 20] [60, 1685] [1, 36]
[55, 60] -> [80, 36] [80, 1685] [1, 55]
[112, 84] -> [140, 84] [80, 140, 1685] [1, 55, 112]
[140, 80] -> [160, 112] [160, 1685] [1, 55]
[160, 320] -> [320, 64] [64, 1685] [1, 55]
[64, 23] -> [65, 55] [65, 1685] [1, 23]
[65, 130] -> [130, 26] [26, 1685] [1, 23]
[26, 7] -> [25, 23] [25, 1685] [1, 7]
[120, 40] -> [120, 104] [25, 104, 1685] [1, 7, 40]
[72, 104] -> [120, 40] [25, 120, 1685] [1, 7, 72]
[120, 240] -> [240, 48] [25, 48, 1685] [1, 7, 72]
[89, 48] -> [100, 72] [25, 100, 1685] [1, 7, 89]
[100, 25] -> [95, 89] [95, 1685] [1, 7]
[35, 95] -> [85, 7] [85, 1685] [1, 35]
[85, 170] -> [170, 34] [34, 1685] [1, 35]
[34, 13] -> [35, 29] [29, 1685] [1, 13]
[168, 126] -> [210, 126] [29, 210, 1685] [1, 13, 168]
[210, 120] -> [240, 168] [29, 240, 1685] [1, 13, 120]
[336, 252] -> [420, 252] [29, 240, 420, 1685] [1, 13, 120, 336]
[420, 240] -> [480, 336] [29, 480, 1685] [1, 13, 120]
[480, 960] -> [960, 192] [29, 192, 1685] [1, 13, 120]
[181, 192] -> [260, 120] [29, 260, 1685] [1, 13, 181]
[500, 1000] -> [1000, 200] [29, 200, 260, 1685] [1, 13, 181, 500]
[475, 200] -> [500, 400] [29, 260, 400, 1685] [1, 13, 181, 475]
[400, 300] -> [500, 300] [29, 260, 500, 1685] [1, 13, 181, 475]
[500, 125] -> [475, 445] [29, 260, 445, 1685] [1, 13, 125, 181]
[260, 445] -> [475, 125] [29, 475, 1685] [1, 13, 181]
[525, 175] -> [525, 455] [29, 455, 475, 1685] [1, 13, 175, 181]
[455, 935] -> [925, 175] [29, 475, 925, 1685] [1, 13, 181, 935]
[475, 925] -> [935, 197] [29, 197, 1685] [1, 13, 181]
[197, 29] -> [175, 181] [175, 1685] [1, 13]
[256, 192] -> [320, 192] [175, 320, 1685] [1, 13, 256]
[360, 320] -> [480, 256] [175, 480, 1685] [1, 13, 360]
[480, 960] -> [960, 192] [175, 192, 1685] [1, 13, 360]
[431, 192] -> [460, 360] [175, 460, 1685] [1, 13, 431]
[196, 147] -> [245, 147] [175, 245, 460, 1685] [1, 13, 196, 431]
[245, 140] -> [280, 196] [175, 280, 460, 1685] [1, 13, 140, 431]
[280, 460] -> [500, 140] [175, 500, 1685] [1, 13, 431]
[500, 175] -> [505, 431] [505, 1685] [1, 13]
[505, 1685] -> [1415, 13] [1415] [1]
[600, 200] -> [600, 520] [520, 1415] [1, 200]
[360, 520] -> [600, 200] [600, 1415] [1, 360]
[600, 1200] -> [1200, 240] [240, 1415] [1, 360]
[445, 240] -> [500, 360] [500, 1415] [1, 445]
[500, 75] -> [445, 459] [459, 1415] [1, 75]
[405, 810] -> [810, 162] [162, 459, 1415] [1, 75, 405]
[162, 459] -> [405, 27] [27, 1415] [1, 75]
[86, 27] -> [85, 75] [85, 1415] [1, 86]
[75, 150] -> [150, 30] [30, 85, 1415] [1, 75, 86]
[30, 85] -> [75, 5] [5, 1415] [1, 86]
[140, 280] -> [280, 56] [5, 56, 1415] [1, 86, 140]
[133, 56] -> [140, 112] [5, 112, 1415] [1, 86, 133]
[112, 84] -> [140, 84] [5, 140, 1415] [1, 86, 133]
[140, 5] -> [115, 133] [115, 1415] [1, 86]
[115, 230] -> [230, 46] [46, 1415] [1, 86]
[103, 46] -> [110, 86] [110, 1415] [1, 103]
[280, 210] -> [350, 210] [110, 350, 1415] [1, 103, 280]
[350, 200] -> [400, 280] [110, 400, 1415] [1, 103, 200]
[400, 800] -> [800, 160] [110, 160, 1415] [1, 103, 200]
[130, 160] -> [200, 80] [80, 110, 1415] [1, 103, 130]
[80, 110] -> [130, 46] [46, 1415] [1, 103]
[120, 40] -> [120, 104] [46, 104, 1415] [1, 40, 103]
[72, 104] -> [120, 40] [46, 120, 1415] [1, 72, 103]
[110, 120] -> [160, 72] [46, 160, 1415] [1, 103, 110]
[224, 168] -> [280, 168] [46, 160, 280, 1415] [1, 103, 110, 224]
[280, 160] -> [320, 224] [46, 320, 1415] [1, 103, 110]
[320, 640] -> [640, 128] [46, 128, 1415] [1, 103, 110]
[128, 46] -> [130, 110] [130, 1415] [1, 103]
[112, 84] -> [140, 84] [130, 140, 1415] [1, 103, 112]
[140, 80] -> [160, 112] [130, 160, 1415] [1, 80, 103]
[130, 160] -> [200, 80] [200, 1415] [1, 103]
[600, 200] -> [600, 520] [520, 1415] [1, 103]
[520, 1415] -> [1265, 103] [1265] [1]
[120, 40] -> [120, 104] [104, 1265] [1, 40]
[72, 104] -> [120, 40] [120, 1265] [1, 72]
[168, 126] -> [210, 126] [120, 210, 1265] [1, 72, 168]
[210, 120] -> [240, 168] [240, 1265] [1, 72]
[145, 240] -> [260, 72] [260, 1265] [1, 145]
[364, 273] -> [455, 273] [260, 455, 1265] [1, 145, 364]
[455, 260] -> [520, 364] [520, 1265] [1, 145]
[520, 1265] -> [1175, 145] [1175] [1]
[750, 1500] -> [1500, 300] [300, 1175] [1, 750]
[300, 850] -> [750, 50] [50, 1175] [1, 850]
[900, 50] -> [750, 850] [750, 1175] [1, 900]
[750, 1500] -> [1500, 300] [300, 1175] [1, 900]
[1025, 300] -> [1000, 900] [1000, 1175] [1, 1025]
[1000, 2000] -> [2000, 400] [400, 1175] [1, 1025]
[400, 1175] -> [1025, 55] [55] [1]
[300, 600] -> [600, 120] [55, 120] [1, 300]
[285, 120] -> [300, 240] [55, 240] [1, 285]
[240, 155] -> [285, 187] [55, 187] [1, 155]
[105, 35] -> [105, 91] [55, 91, 187] [1, 35, 155]
[91, 187] -> [185, 35] [55, 185] [1, 155]
[55, 185] -> [155, 1] [] []

$\endgroup$
3
  • $\begingroup$ This is long and I didn't check everything, but the first few are correct. To be honest I am pretty surprised that the answer is yes. $\endgroup$ Nov 27, 2015 at 17:43
  • $\begingroup$ Congratulations! I will award the bounty as soon as I verify your solution. @Haobin, did you know there was a solution when you posted the question? Is this similar to your own solution? I'd be very interested in reading any mathematical explanation of why those two particular equations were chosen for the problem, and whether there is a mathematical proof showing how this can be done. $\endgroup$ Nov 27, 2015 at 18:30
  • $\begingroup$ @Sleafar Dammit, I had a very similar idea but you beat me to it :-) Nicely done! $\endgroup$ Nov 27, 2015 at 18:47
-2
$\begingroup$

I believe that no.

For many pairs of numbers x and y, (4x + 3y) / 5 and (24x − 7y) / 25 won't even be integers. For example:

x = 2, y = 7: 
   (4x + 3y) / 5 = (8 + 21) / 5 = 29/5 = 5.8
   (24x − 7y) / 25 = (48 - 49) / 25 = -1/25 = -0.04

In about only 1/5 of the steps the first expression will be an integer, and in about only 1/25 of the steps the second expression will be an integer, per divisibility rules, and assuming that the numerator is a random integer.

And, by construction, most non-integer numbers will continue to be operated into other non-integer numbers - with bigger denominators in fractional form.

The question can be turned around into: Find a way to generate all numbers from 1 to 2014, given the operations with x and y above, and choosing x and y for each step. Expecting it to happen at random is extremely improbable.

$\endgroup$
1
  • 3
    $\begingroup$ I don't think anyone is expecting it to happen at random. The question asks, "is it possible?". Thus if there is any possible selection of numbers that leads to the sequence $1...2014$, the answer is "Yes." Indicating that it won't likely happen randomly is stating the obvious. $\endgroup$ Nov 26, 2015 at 23:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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