27
$\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$
  • 11
    $\begingroup$ I assume that $(3,4,5)$ and $(7,24,25)$ being Pythagorean triples has something to do with the solution... $\endgroup$ – GentlePurpleRain Oct 15 '15 at 19:26
  • 11
    $\begingroup$ Also possibly relevant: $(\frac{4i+3}{5})^2=\frac{24i-7}{25}$ $\endgroup$ – f'' Oct 15 '15 at 23:18
  • 11
    $\begingroup$ Are we assuming all the numbers are integers? Do fractions get written up, or are they rounded? $\endgroup$ – Callum Bradbury Oct 16 '15 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 '15 at 17:26
  • 4
    $\begingroup$ @Haobin Do you know the answer? $\endgroup$ – ghosts_in_the_code Oct 25 '15 at 15:43
13
+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$
  • $\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$ – Fimpellizieri Nov 27 '15 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$ – GentlePurpleRain Nov 27 '15 at 18:30
  • $\begingroup$ @Sleafar Dammit, I had a very similar idea but you beat me to it :-) Nicely done! $\endgroup$ – Carl Löndahl Nov 27 '15 at 18:47
-2
$\begingroup$

To answer this question, I took a different route than most (and I am assuming it is not encouraged by the site): bruteforcing. I felt this was the best way to at least start understanding the pattern it follows and then I could go from there to see WHY the pattern is the way it is. I am fairly sure my code is free from errors. I added some comments so you can make some sense to my mess:

This is in python 2.7:

from random import randrange as choice 
import sys

sys.setrecursionlimit(1000000) 
NUMBERSLIST = range(2,2016)
TEST = range(1,2015)


def test(numlist): #Tests to see if our list of numbers is the goal list
    for n in range(0,2014):
        if numlist[n] != TEST[n]:
            return
    print "TRUE! \nClosing..."
    raise SystemExit

def main(numlist): # performs the calculations 
    l = 2014
    n1 = choice(0,l) # chooses x
    while True: # this is to makes sure that x and y are not the same
        n2 = choice(0,l) # chooses y
        if n2 != n1:
            break
    new1 = round(  (4*numlist[n1]   +   3*numlist[n2])  /  5)  #yes, I rounded these. It does not need to be that accurate to see the pattern in the numbers
    new2 = round(  (24*numlist[n1]   -   7*numlist[n2])  /  25)

    numlist[n1] = new1
    numlist[n2] = new2

    if numlist[0] == 1: #The first value must be 1
        if numlist[1] == 2: #The second value must be 2
            if numlist[2] == 3:
                test(numlist)
    return numlist


i = 0L
while True:
    i +=1
    NUMBERSLIST = main(NUMBERSLIST) # runs the function main
    if i%100000 == 0: # every hundred thousand times, it tells "false" and then the number of times it has done the process
        print "false " + str(i)
        if i%10000000 == 0: # every ten million times it prints the list
            print NUMBERSLIST

As I said, it prints out the list every 10,000,000 times, and, it turns out, the numbers just keep increasing (or decreasing) until they reach infinity. By the 10 millionth time, each number is 173 to 175 digits long (positive or negative). By the 20 millionth, it was too large for my computer.

To answer the question: No. It does not. The sequence will never be in order of 1, ... , 2014. Sorry if this was not the proper way to answer a question on this site. I would assume a puzzle site would not encourage using a computer for a puzzle, but I feel that to at least begin this question, I needed to know what the calculation did to the numbers over many iterations. Now that I know that it is not even a possibility, there was no need to see why.

Note: I did not answer this for the bounty. I just thought it was an intriguing question.

$\endgroup$
  • 6
    $\begingroup$ This only proves that by randomly selecting numbers, you end up with ever-increasing numbers. Perhaps if numbers are very specifically selected, this pattern will not hold true. It appears that in general (not necessarily always), if $x<y$ then $x+y > \frac{4x+37}5 + \frac{24x-7y}25$, which means the numbers will approach $0$ over time. $\endgroup$ – GentlePurpleRain Nov 25 '15 at 18:36
-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$
  • 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$ – GentlePurpleRain Nov 26 '15 at 23:42

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.