Fox 337

This one is related to Fox 334, and should be simpler.

http://www.8foxes.com/

Fox 334

This is more like a google search than a geometry problem, but it is nice to have a reference in our blog as well. Good luck to those who want to try!

http://www.8foxes.com/

Balanced Mancala Problem

We rarely ask pure math problems but here is one with a "very little" touch of geometry. This does not need to be defined as a mancala game, but here it goes:

We have stones coming in batches. Each stone has a color and a weight. If the color of a stone is:

Yellow: It must be placed every other pit (every 2 pits) Batch size is always: 6 Total batches: y Total number = 6y

Red: Must be placed every 3 pits Batch size: 4 Total batches: r Total number = 4r

Green: Must be placed every 4 pits Batch size: 3 Total batches: g Total numbers = 3g

Blue: Must be placed every 6 pits Batch size: 2 Total batches: b Total number = 2b

Purple: Must be placed only once in 12 pits Batch size: 1 Total batches: p Total numbers = p

So there are N=6y+4r+3g+2b+p many stones. The stones in the same batch have the same weight. Different batches may have different weights. WLOG, assume that all weights are integers. We have a proof that ending up with the best well-balanced mancala is very difficult (NP-Hard). Here "well-balanced" means that the pit with the maximum weight is minimized when all stones are distributed. Let's call this maximum pit weight as W.

Consider the following heuristic process:

Step 1. Sort the batches with respect to their weights (batches with the high-weight stones go first) Step 2. Insert the first batch starting from pit number 1. Step 3. Insert the next batch in a way that the total maximum weight throughout 12 pits remains minimum. Step 4. Repeat Step 3 until all batches are placed in the mancala. Let H be the maximum weight throughout 12 pits.

A simple Example: Suppose we have only 4 batches: Yellow (6 stones, each 45 grams) Blue (2 stones, each 40 grams) Yellow (6 stones, each 30 grams) Green (3 stones, each 20 grams) First batch (Yellow) goes to pits: 1, 3, 5, 7, 9, and 11. H=45. Second batch (Blue) goes to pits: 2 and 8. H=45. Third batch (Yellow) goes to pits: 2, 4, 6, 8, 10, and 12. H=70. Fourth batch (Green) goes to pits: 3, 7, and 11. H=70.

In this exercise, heuristic actually finds the optimum, i.e., H=W=70 grams, observed in pits 2 and 8.

And the question: Prove that the worst-case of the heuristic solution, H, is always less than 2W. In other words, W ≤ H ≤ 2W always holds. If you disagree, then try to generate a counter-example.

Good luck!

Fox 320 - Solutions

This fox has been discussed extensively. See here...

1. Calculus by Bleaug

He says: "I spotted this problem in a Paul Halmos book "Problems for mathematicians, young and old, 1991", actually in a French translation. He provided the solution below (reformulated by myself) as being proposed by Hugh Montgomery in 1985 in some Math Conference."






2. Checkerboard Solution by Rochberg and Stein:

1. Call sub rectangles as TILEs.


2. Start from the lower left corner of the overall rectangle (let's call this point as the origin)Draw horizontal and vertical lines separated by 1/2=0.5 units starting from the origin.


3. This will create 0.5 x 0.5 squares (and possibly rectangles around 2 edges -top and/or RHS)


4. Color the first square (that has the origin as one of its corners) as black the next one as white, and so on to generate a checkerboard-look.


5. Each TILE will have equal areas of black and white (Why?)


6. Therefore the overall rectangle will have equal areas of black and white.


7. So overall rectangle has at least one integer side.
   

H means the horizontal side is integer, and V means that the vertical side is integer. a1 is the square at the origin. There could have been a smarter combination, but this simple one illustrates the process clearly. This looks like the closest geometric solution we can get -at this time.

When there's hardly no day nor hardly no night
There's things half in shadow and halfway in light

3. Induction by Robinson

1. Assume that each H-tile has a width of 1, and each V-tile has a height of 1. Note that any rectangle can be converted this way without distorting the original problem. (This may increase the number of tiles significantly though)


2. Chose any H-tile, say T(0). (If there is no H-tile, then the result is immediate)


3. If there are H-tiles whose lower border shares a segment with T(0)'s upper border, choose one and call it T(1).


4. Otherwise only V-tiles share this border. In this case, we can expand T(0) upward 1 unit. This does not increase the number of H-tiles. Also, the cut V-tiles still have height 1. (They are still V-tiles)


5. Continue expanding T(0) until either the top of the rectangle is reached or a choice of an adjacent H-tile T(1) is possible.


6. Then repeat the same process from T(1). (Continue upward similarly from T(1) to get T(2), and so on...)


7. This will result in a chain of T(0), T(1), T(2), ... , T(m).


8. Starting from T(0) again, work downward similarly to obtain a bigger chain:
   T(-n), T(1-n), ... , T(0), T(1), ... , T(m-1), T(m) of H-tiles stretching from bottom to top.


9. Remove these tiles and slide the rest together to get a rectangle with fewer H-tiles.


10. Induction applied to this smaller rectangle yields the result for the original rectangle.
    

http://www.8foxes.com/

Fox 320

Bleaug has a solution for this general case.

http://www.8foxes.com/

Fox 313

Bleaug submitted the following fox, saying: "a problem which can be expressed in geometric terms and that is elegantly solved using pure algebraic arguments, still giving deep insight."

General case of this problem can be found in literature (with at least 14 proofs :)
But let's try this smaller version here.

http://www.8foxes.com/

An Interesting Property of Relatively-Prime Numbers

Hello Guys,
There are a few more parabola questions in line, but I need to solve a number theory question. I have a proof but it is very long and clumsy. I am looking for a slicky solution. Here it goes:

a and b are relatively-prime integers such as,
3 and 8 (e.g. GCD(3,8)=1).
Let N=ab.
Let 1 ≤ k ≤ a, and 1 ≤ m ≤ b, both are integers.
Let set A be all integers, x=k+ia AND x ≤ N AND i=0,1,...
Let set B be all integers, y=m+jb AND y ≤ N AND j=0,1,...

PROVE THAT A∩B contains one integer only.

Example:
a=3, b=8, GCD(3,8)=1
N=24
Let k=2 and m=6.
A={2, 5, 8, 11, 14, 17, 20, 23}
B={6, 14, 22}
A∩B={14}
Note that the above statement is true for any k and m satisfying
1≤k≤a, and 1≤m≤b respectively.

It is very obvious that there should be a short and beautiful proof.