Little math problems September 2018

[pier4r]

A little one, that nonetheless is nice (and maybe someone can extend it to make it more challenging).
There are 15 white balls and 13 black balls in a box. Plus spare white and black balls.
One picks 2 balls at random.
If those are both white or black, a white ball is inserted in the box, those picked are removed.
If the colors are different, a black ball is inserted in the box. Those picked are removed.
You do the process until you end up with only one ball in the box. What color is it?

Bonus: do a calculator program that goes through the possible states of the bag and picks.

A second little one:
Find two positive integers such that: the sum of whose squares is a cube and the sum of whose cubes is a square.
I know only one family of them, if you find more, great.

Bonus: a calculator program that checks all those under, say, 1 million (each integer can vary from 1 to 1million). The faster the better (each device used will made its own category).

Credit: mathjam

answers with spoilers like this

Code:


SPOILER ALERT
SPOILER ALERT
SPOILER ALERT
SPOILER ALERT








solution

[Thomas Klemm]

Code:

SPOILER ALERT











These are the changes to white and black balls based on the color of the two chosen balls:
WW: W -= 1
BB: W += 1, B -= 2
WB or BW: W -= 1

We can see that number of black balls can only be reduced by 2 thus we end up with 1 black ball.
From now on the number of white balls can only be reduced. Thus we end up with 1 black ball.

Bonus: A Python program that simulates the process.

Code:

SPOILER ALERT











from random import choice

bag = ["W"] * 15 + ["B"] * 13

while len(bag) > 1:
    first = choice(bag)
    bag.remove(first)
    second = choice(bag)
    bag.remove(second)
    both = first + second
    if both == "WW" or both == "BB":
        bag.append("W")
    else:
        bag.append("B")
    print first, second, bag

The result of a typical run:

Code:

SPOILER ALERT












W B ['W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B']
W B ['W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B']
B W ['W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B']
W B ['W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B']
B B ['W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'W']
W W ['W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'W', 'W']
W W ['W', 'W', 'W', 'W', 'W', 'W', 'W', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'W', 'W', 'W']
W W ['W', 'W', 'W', 'W', 'W', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'W', 'W', 'W', 'W']
B W ['W', 'W', 'W', 'W', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'W', 'W', 'W', 'W', 'B']
W W ['W', 'W', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'W', 'W', 'W', 'W', 'B', 'W']
B B ['W', 'W', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'W', 'W', 'W', 'W', 'B', 'W', 'W']
B B ['W', 'W', 'B', 'B', 'B', 'B', 'B', 'B', 'W', 'W', 'W', 'W', 'B', 'W', 'W', 'W']
B W ['W', 'B', 'B', 'B', 'B', 'B', 'W', 'W', 'W', 'W', 'B', 'W', 'W', 'W', 'B']
W B ['B', 'B', 'B', 'B', 'W', 'W', 'W', 'W', 'B', 'W', 'W', 'W', 'B', 'B']
B B ['B', 'B', 'W', 'W', 'W', 'W', 'B', 'W', 'W', 'W', 'B', 'B', 'W']
B B ['W', 'W', 'W', 'W', 'B', 'W', 'W', 'W', 'B', 'B', 'W', 'W']
W W ['W', 'W', 'B', 'W', 'W', 'W', 'B', 'B', 'W', 'W', 'W']
W B ['W', 'W', 'W', 'W', 'B', 'B', 'W', 'W', 'W', 'B']
W B ['W', 'W', 'W', 'B', 'W', 'W', 'W', 'B', 'B']
W W ['W', 'B', 'W', 'W', 'W', 'B', 'B', 'W']
B B ['W', 'W', 'W', 'W', 'B', 'W', 'W']
W W ['W', 'W', 'B', 'W', 'W', 'W']
W W ['B', 'W', 'W', 'W', 'W']
W W ['B', 'W', 'W', 'W']
W W ['B', 'W', 'W']
B W ['W', 'B']
W B ['B']

Thanks for the challenge
Thomas

[Albert Chan]

Code:


White ball / black ball puzzle ...

SPOILER ALERT
SPOILER ALERT
SPOILER ALERT
SPOILER ALERT





It does not matter what is drawn, black ball remaining is always odd
So, last ball remaining must be black

[Albert Chan]

Code:


Sum of squares = cube, sum of cubes = square puzzle ...

SPOILER ALERT
SPOILER ALERT
SPOILER ALERT
SPOILER ALERT




Smallest positive integer pair should be (2,2). 4 + 4 = 8, 8 + 8 = 16
Doing brute force for a <= b < 10000, these work too (besides 2,2)

128, 128 = 2*4^3, 2*4^3
625, 1250 = 5^3, 2*5^3
1458, 1458 = 2*3^3, 2*3^3
8192, 8192 = 2*16^3, 2*16^3

Edit: found the general form of sum of 2 squares a cube. Not sure if it cover all cases ...

[ijabbott]

Balls!

Code:


SPOILER ALERT
SPOILER ALERT
SPOILER ALERT
SPOILER ALERT








The puzzle with the balls has a degenerate case. Suppose that all pairs picked are matching
pairs until the box is left with only an unmatched pair. This must be removed on the next pick and
replaced with a single black ball. Therefore, the remaining ball is black.

Sometimes if you know the puzzle has a single answer, it is easier to consider the simplest way to get to that answer, rather than consider all ways of getting to the answer. Like with the "remaining volume of a sphere with a six inch tall cylinder cut through the centre" puzzle, you know it has a single answer, and the simplest way of getting to the answer is to consider the degenerate case.

[Albert Chan]

Hi, ijabott

Using degenerate case to guess the answer is good.
However, the puzzle might be sneaky, without an unique solution.

When I was in school, my math teacher is famous to do that in exam.
You get better grade if you pick ... none of the above

[Valentin Albillo]

.
Hi, Pier:

(09-20-2018 11:21 AM)pier4r Wrote:  Find two positive integers such that: the sum of whose squares is a cube and the sum of whose cubes is a square.

There are several ways to attack this problem depending on the particular mix of brute force and theory one wants to employ. The fastest, more thoughtful way is to use congruences and subsequent parameterization while the easiest way, the one which requires less thinking and math foreknowledge, is simply to use brute force with or without additional finesses to reduce the running times.

A simple 12-line program (503 bytes, 70% brute force + 30% finesse) for the HP-71B quickly produces all 7 unique (up to x-y symmetry) solutions for z in [1, 2000], namely:

      (2,2), (128, 128), (1250, 625), (1458, 1458), (8192, 8192), (31250, 31250), (80000, 40000)

and infinitely more can be found by simply expanding the search range, though at this point it's more efficient (albeit more convoluted) to begin using congruences and parameterization, as stated.

Another way to proceed is to perform algebraic manipulations using divisibility criteria. It quickly gets somewhat laborious for the general case but for a relevant particular case it's dead easy and it allowed me to create a simple 20ish-step RPN program which runs on every classic RPN machine from the HP-10 or HP-25C to the HP42S, say, and which will produce in seconds exact solutions up to 10-digit or 12-digit long, depending on the machine.

The version for the HP-15C is just 19 steps and produces 41 solutions ranging from (2,2) to (9500208482, 9500208482):

      9500208482 ^ 2 + 9500208482 ^ 2 = 180507922402929488648 = 5651522 ^ 3
      9500208482 ^ 3 + 9500208482 ^ 3 = 1714862895480508549701652312336 = 1309527737575844 ^ 2

The version for the HP42S is similarly compact and produces 89 solutions, again in seconds, ranging from (2,2) to (993962581922, 993962581922):

      993962581922 ^ 2+993962581922 ^ 2 = 1975923228522097122428168 = 125484482 ^ 3
      993962581922 ^ 3+993962581922 ^ 3 = 1963993753901477688038748399260378896 = 1401425614829940836 ^ 2

Finally, using a version of this same RPN program for multiprecision software you can produce solutions of any size, say:

      7081411940532321969341507101262893738689268797761826852357921359507223378 ^ 2 +
      7081411940532321969341507101262893738689268797761826852357921359507223378 ^ 2=

            10029279014302749179904378265599862005294195018425352469280088087093653074
            3348010035520988277313336460873377556821353492473182309595873918379461768

                  = 4646114457816754433119112162063873699817342813282 ^ 3

      7081411940532321969341507101262893738689268797761826852357921359507223378 ^ 3+
      7081411940532321969341507101262893738689268797761826852357921359507223378 ^ 3=

            71021456166813724373369160917786492001894725287832594459295292562401596433
            91012000742769466486927456148133623926599939967004913734032030065738557704
            01365222261117051148735876729922150054442435311887353433629595786812304

                  =

                  266498510627758901877702659634170893109466921127927695666500424568907165355
                  87505472077470689588260565184577452 ^ 2

and of course it's equally easy to derive similar algorithms for other particular cases and use them to create additional small RPN programs to produce many more solutions very quickly.

Thanks for the interesting mini-challenge and best regards.
V.
.

[Albert Chan]

(09-24-2018 12:53 AM)Valentin Albillo Wrote:        (2,2), (128, 128), (1250, 625), (1458, 1458), (8192, 8192), (31250, 31250), (80000, 40000)

and infinitely more can be found by simply expanding the search range, though at this point it's more efficient
(albeit more convoluted) to begin using congruences and parameterization, as stated.

Is there a pattern to the solution pairs ?
For above, it seems to be (2 N^3, 2 N^3) or (2 N^3, N^3).

Quote:Another way to proceed is to perform algebraic manipulations using divisibility criteria ...

What divisibility criteria did you end up using ?

[Valentin Albillo]

.
Hi, A.Chan:

(09-24-2018 12:18 PM)Albert Chan Wrote:  

(09-24-2018 12:53 AM)Valentin Albillo Wrote:        (2,2), (128, 128), (1250, 625), (1458, 1458), (8192, 8192), (31250, 31250), (80000, 40000)

and infinitely more can be found by simply expanding the search range, though at this point it's more efficient (albeit more convoluted) to begin using congruences and parameterization, as stated.

Is there a pattern to the solution pairs ? For above, it seems to be (2 N^3, 2 N^3) or (2 N^3, N^3).

There's an infinity of solutions that do not fit that particular pattern, for instance ( 3430000, 10290000 ):

      3430000 ^2 + 10290000 ^2 = 117649000000000 = 49000 ^3
      3430000 ^3 + 10290000 ^3 = 1129900996000000000000 = 33614000000 ^2

Quote:What divisibility criteria did you end up using ?

It depends on the particular case being analyzed.

Regards.
V.
.

[Albert Chan]

(09-20-2018 02:37 PM)Albert Chan Wrote:  Edit: found the general form of sum of 2 squares a cube. Not sure if it cover all cases ...

It only take 1 counter-example to dis-prove a conjecture ...

3430000^2 + 10290000^2 = 49000^3 proved the pattern (2 N^3, 2 N^3), (N^3, 2 N^3) were wrong.

This counter-example also proved above link does not cover all cases for two squares sum to a cube:

(A^3 - 3 A B^2)^2 + (3 A^2 B - B^3)^2 = (A^2 + B^2)^3

Searching all integers A, B, 0 <= A <= B, and A^2 + B^2 = 49000, we have 2 solutions.

A, B = 70 , 210 ---> 6174000^2 + 8918000^2 = 49000^3
A, B = 126, 182 --> 2639728^2 + 10520496^2 = 49000^3

Since it is unable to generate the counter-example, the formula does not cover all cases.

[pier4r]

Nice find

[Valentin Albillo]

(09-25-2018 10:56 AM)pier4r Wrote:  .
Nice find
.

Some questions, if you don't mind:

1) Who are you replying to, Albert or me ?

2) Nothing else ? No comments on the solutions posted ?

3) In your OP you said you knew only one family of solutions (I've found several). Will you care to elaborate or are you still waiting for additional posts ?

Regards.
V.
.

[pier4r]

1) albert commenting his own post.

2) Sorry I thought it was not needed. I find all the effort put into solutions neat. Of course even further explorations are appreciated. I find that good(great/outstanding/etc..) contributions are good even without comments. A good contribution is not good only when commented.

3) I guess I claimed too early something I (and the other guys at the math jam) didn't test enough. At the math jam I observed (the other guy did it too independently and then we confronted the solutions n1) the following:

Code:



I
forgot
the
spoiler
alert









2^2 + 2^2 = 8 = 2^3
2^3 + 2^3 = 16 = 2^4 = (2^2)^2

2^8 + 2^8 = 2*2^8 = 2^9 = (2^3)^3 
2^9 + 2^9 = 2*2^9 = 2^10 = (2^5)^2 

so we quickly settled on (we didn't test much) odd powers of two as exponent.

2^32 + 2^32 = 2*2^32 = 2^33 = (2^11)^3
2^33 + 2^33 = 2*2^33 = 2^34 = (2^17)^2 

2^128 + 2^128 = 2*2^128 = 2^129 = (2^43)^3
2^129 + 2^129 = 2*2^129 = 2^130 = (2^65)^2

2^512 + 2^512 = 2*2^512 = 2^513 = (2^171)^3
2^513 + 2^513 = 2*2^513 = 2^514 = (2^257)^2

2^(2^(2k+1)) + 2^(2^(2k+1)) = 2*2^(2^(2k+1)) = 2^(2^(2k+1)+1)
Now indeed we didn't prove that 2^(2k+1)+1 is always a multiple of 3.
2^(2^(2k+1)+1) + 2^(2^(2k+1)+1) = 2*2^(2^(2k+1)+1) = 2^(2^(2k+1)+2)
While 2^(2k+1)+2 , still we didn't really check at the time, is a multiple of 2.

If 2^(2k+1)+1 is a multiple of 3 always, then there is a family of solutions. I will check later.

n1: the idea at the math jam is to work on a problem on your own, then share the solutions and double check them. If everyone is stuck, then brainstorming together.

update: what the solutions in this threads shows is that there seems to be other fitting numbers as well. We had only pen + paper in a bar at the mathjam so we didn't stay on the problem too long.

[Valentin Albillo]

.
Understood, thanks.
V.
.

[Albert Chan]

Using (2,2) as base, one general solution for square / cube puzzle:
Below equality work for all non-negative integer n:

(2⁶ⁿ⁺¹)² + (2⁶ⁿ⁺¹)² = 2¹²ⁿ⁺³ = (2⁴ⁿ⁺¹)³
(2⁶ⁿ⁺¹)³ + (2⁶ⁿ⁺¹)³ = 2¹⁸ⁿ⁺⁴ = (2⁹ⁿ⁺²)²

Edit: For *all* base (a,b), positive integer k, scale up k⁶ will work.

So, Valentin big examples (post #7) automatically work, because base = (2,2):

9500208482 = 2 * 41^6
993962581922 = 2 * 89^6
7081411940532321969341507101262893738689268797761826852357921359507223378 = 2 * 1234567890123^6

Looking at above k = 1234567890123, seems Valentin already know this

[pier4r]

Albert nice contribution but you need to use the 12n+3 in the second case, not again 6n+1. Anyway you end up with 12n+4 that works

[Albert Chan]

Hi, pier4r

I think my math is right ...

Second formula is to check sum of cubes = a perfect square
Since both terms are the same, binary exponent = 1 + 3 * (6n + 1) = 18 n + 4
Sum of cubes binary exponent is even, thus perfect square.

You can also think of 2⁶ⁿ⁺¹ = 2 * (2ⁿ)⁶, so k = 2ⁿ

If (a, b) is a solution, sum of squares of (k⁶ a, k⁶ b) = cube * k¹² , also a cube
Similarly, sum of cubes of (k⁶ a, k⁶ b) = square * k¹⁸, still a square.

Actually, k can be any integers, not just 2ⁿ

[pier4r]

True, I mixed the statement. So actually what we found in the mathjam solves another problem.

[Albert Chan]

(09-25-2018 12:48 AM)Valentin Albillo Wrote:         3430000 ^2 + 10290000 ^2 = 117649000000000 = 49000 ^3
      3430000 ^3 + 10290000 ^3 = 1129900996000000000000 = 33614000000 ^2

This is how above solution (a, 3 a) is obtained:

3² + 1 = 10 = 2 * 5
3³ + 1 = 28 = 2² * 7

So, a may be the form 2^x 5^y 7^z
Sum of square = 2^2x+1 5^2y+1 7^2z
Sum of square is cube, thus x=1, y=1, z=0 (modulus 3)

Sum of cubes = 2^3x+2 5^3y 7^3z+1
Sum of cubes is square, thus x=0, y=0, z=1 (modulus 2)

Minimum (x, y, z) that satisfy both => (4, 4, 3), thus a = 2⁴ 5⁴ 7³ = 3430000