The problem battles

[nick-o-matic]

On problem battles the ballemaker posts any kind of problem or puzzle (it can be mathematical, verbal, logical, physical...) and the first one to solve the problem wins the battle!

I'll start a bit tricky one. If you are good at sudokus you can propably solve this one too. Here are the instructions and here is the problem itself. The symbols to use in this one are 1,2,3,4,5,6 and 7 and on the squares with the same colour the number is the same. Also I have given some of the squares with the right answer ready.

[Igge]

in your example, one diagonal is "c, c, c" how is this possible, if that line should aswell consist of the letter a, b, c?

[nick-o-matic]

in your example, one diagonal is "c, c, c" how is this possible, if that line should aswell consist of the letter a, b, c?

Oops yes there is I knew I would mess up something I made those instructions very quickly.
But it seems you understood the idea.

Anyway, the problem itself isn't made by me so you should be able to go solving it without fear of some mongo mistakes like impsy to solve. I also checked many times I copied it right from a problem book.

[Igge]

kk :D

cant try it atm, but will write it down on a paper and try later today. hopefully no one will have solved it by the time im done.

[nick-o-matic]

Btw, just noticed it's impsy to make 3 x 3 crossword with these rules. Proof: if you set the first line A, B and C, it will look like this:

ABC
XXX
XXX

Now the X below B cant be B (obv), nor A (because the line from left up to down right would be AAX) nor C (because the line from right up to down left would be CCX), so the problem is impsy.
Managed to make 4 x 4 crossword though and my solution seems to be the only possible one at 4 x 4. This could be the battle b to you if the original gets solved.

[Smibu]

1476325
7254136
6543271
5327614
3761542
2135467
4612753

At one point I thought this is impsy, but wasn't after all, didn't have to guess any of the numbers :)
Too late, Igge :P (unless I have mistakes in there)

[nick-o-matic]

Excellent, that looks like right

Now a new battle: 54321 x ***** = *****12345

("*****" is a 5-number number and *****12345 is a 10-number and its 5 last desimals are 1,2,3,4 and 5)

Now solve all the *'s.

[Smibu]

54321*99945=5429112345
This was much easier :P

[nick-o-matic]

Nice. This should be haard:

Fill the following "magic square" so that every line's total sum is 2001:

X1X
XXX
XX2

Here is an excample of magic squares.

[welle]

1332 1 668
3 667 1331
666 1333 2

[wjelo]

1337

[nick-o-matic]

Nice, correct. =)

Now someone else to post a problem?

[Smibu]

Okay - this is a long one:
By using the integers 1, 2, 3 and 4 AND by using certain mathematical operators, try to get as many other integers in a closed interval [-100,100] as possible. I think I said that pretty badly, here's an example:
1+2+3+4=10 (ok)
1-2-3-4=-8 (ok)
1*(2+3)^4=625 (NOT ok because 625>100)
(1+2+3)/4=1.5 (NOT ok because 1.5 is not an integer)
1+1+2+3+4=11 (NOT ok because you used number 1 twice)
74 (NOT ok because the whole expression is missing, these "NOT ok" expressions actually decrease your points, see below)

So now the result you get would be 2 integers (10 and -8).

Every expression MUST contain all 4 numbers. For example, 1+2+3=6 is NOT allowed because there is no 4 in it.
You may only use the minus sign WITH SUBTRACTION. That means -3+2+1+4=4 is NOT allowed (you can't start the expression with a negative number, in other words. And (1+2+3)*-4=-24 isn't allowed either. Instead, (1+2)*(3-4)=-3 is allowed.

ALLOWED OPERATORS:
-plus, +
-minus, -
-multiplication, *
-division, /
-x to the power of y, x^y
-factorial, x!
-brackets (as many as you want), ()

HOW TO GET/LOSE POINTS:
One integer with correct expression=+1 point.
One integer with incorrect expression or no expression at all=-1 point.
Expression containing not allowed operators or other weird things=-1 point.
You can use the expressions I used in the examples, so you don't have to avoid them in vain. So I guess everyone should get at least 3 points
The maximum amount of points that anyone can get is 201, or the maximum may be lower, too, I'm not sure if all integers [-100,100] can be expressed in this way.

BTW: I guess it's best to post your integers (with the expressions of course, like in the first example) to me with a PM to prevent cheating (I can't prevent you from chatting in IRC, though ). Deadline: I'll give 2 weeks, so 25.8.2008 is the last day you can send them.

I hope you got the idea, good luck! Ask if I said something strange or you've got other questions.

EDIT: I changed the interval.

[nick-o-matic]

[-200,200] is something like VERY large range so that people would orka think this carefully I would suggest that you shrank that range very much, maybe [-30,30] or even [-20,20]?

[Smibu]

I think the interval [-50,50] for example is way too easy (the integers that are near 0 are the easiest to figure out). It is harder to express integers closer to 100 or so. I tried this kind of problem a long time ago, and I was able to express almost all integers from 0 to 100 (I didn't try to get negative integers). That did take a while (pretty long) to think, so maybe I'll give you a smaller interval:

NEW INTERVAL: [-100,100]
So max. amount of points is now 201 (or less).

I won't make it smaller than that, otherwise this problem might become too simple. Deadline is same, 25.8.2008 (Monday).
Btw, everyone can tell here how many integers he has managed to express so far. I wasn't able to express some integer in interval [70,79], was it 76 or something, I'm not sure, it was a long time ago I tried this.

[welle]

I found 157 only using the following operators:
+, -, *, !
Will try to find more with a new approach later...

PS: I have only 76 missing in [70,79].

[welle]

i got 187 now and will settle with that. some funny results:
1432 = 1*2*((3!)!-4)
4321 = 1+(2+4)!*3!

this was a nice problem, reminds me of that one: clicky clicky

[zebra]

Are the concatenations of the digits, like 12 + 34, allowed here?

[Smibu]

Are the concatenations of the digits, like 12 + 34, allowed here?

No, you cannot combine digits like that.

[Smibu]

Remember to send your answers today or tomorrow! I won't accept any answers sent on the 26th Aug 2008 at 0:00 or later (GMT).

[zebra]

I got 186 numbers, dunno how welle got 187...

[welle]

nice zebra
in fact i got 188 =P
will share tomorrow if youre interested

[zebra]

nice zebra
in fact i got 188 =P
will share tomorrow if youre interested

yes of course.

[Smibu]

Battle over - results here

1. welle 188 points
2. milagros 187 points
3. zebra 172 points
4. nick-o-matic 167 points

Welle and milagros had no mistakes in expressions, congrats! Zebra had 7 incorrect expressions, and nick-o-matic had 7 incorrect expressions as well.

The integer that welle had but milagros didn't have was -26=2-1-3-4!
Milagros solved integers in [-200,200] but I calculated the points according to [-100,100] :)

Here are everyone's results:

results.zip

(21.58 KiB) Downloaded 128 times

Nick-o-matic sent his answers in pics, here's the links:
http://img82.imageshack.us/my.php?image=p8250255vv2.jpg
http://img142.imageshack.us/my.php?imag ... 257sy0.jpg
http://img261.imageshack.us/my.php?imag ... 256di8.jpg

[milagros]

hah when i was merging results with two methods manually in text file, i skipped that ez -26:))
got some 300+ in -200->200

[welle]

So here's my solution written in java: The class DS (double+string) can store the value d of the expression s. We construct new DS's out of old ones by the recursion given by the allowed operators: add, sub, mul, div, pow, fac. The latter plays a special role, because the faculty is only defined for non-negative integers. Therefore we check d with isFac() to compte the faculty f of d if it exists and isn't computed yet, to return whether it exists or not (without overflow). After combining the given values 1,2,3,4 with these operators we can check with isInt() if they are integers, because we're only looking for those. The method p() might add parantheses to the expression to avoid ambiguities.

Code: Select all

import java.lang.*;

public class DS {
    public double d;
    public String s;
    long f = 0;
    
    public boolean isInt() { return Math.round(d) == d; }
    public boolean isFac() {
        if (d < -0.5 || !isInt()) return false;
        if (f > 0) return true;
        int i, n = (int)Math.round(d);
        for (f = i = 1; i <= n && f <= 1000000; ++i) f *= i;
        if (i > n) return true;
        f = 0;
        return false;
    }
    
    public DS() {}
    public DS(int i) { d = i; s = "" + i; }
    public DS(double D, String S) { d = D; s = S; }

    static String p(String s) { return s.length() <= 2 ? s : "(" + s + ")"; }

    public DS add(DS ds) { return new DS(d + ds.d, p(s) + "+" + p(ds.s)); }
    public DS sub(DS ds) { return new DS(d - ds.d, p(s) + "-" + p(ds.s)); }
    public DS mul(DS ds) { return new DS(d * ds.d, p(s) + "*" + p(ds.s)); }
    public DS div(DS ds) { return new DS(d / ds.d, p(s) + "/" + p(ds.s)); }
    public DS pow(DS ds) { return new DS(Math.pow(d,ds.d),p(s)+"^"+p(ds.s)); }
    public DS fac()      { if (f == 0) isFac(); return new DS(f,p(s) + "!"); }
}

Now we use the string-array s and the index-shifting-method s(.) to store one expression with the value of an integer k in s[s(k)]. Starting with DS's with the values 1,2,3,4 we form every possible expression (with at most two faculties applied to a every single operand) by composing them with the methods named C,D,E, where C calls E with every possible pair of the its arguments in the first two parameters. Then E applies possible faculties to these first two parameters, before they are combined to a new DS in C. Now we have one DS less and can continue in this manner. Finally the single-argument method D(.) stores the formed expression of an DS in the slot of s[] associated by its value, if it's integer and not overwriting a better (e.g. shorter) expression. Now we can iterate s to count and print the expressions we found.

Code: Select all

import java.lang.*;

public class smibu {
    static int MIN = -100;
    static int MAX =  100;
    static int L   = MAX - MIN + 1;

    static String[] s = new String[L];

    static int       s(long i) { return (int) (i - MIN); }
    static boolean isIn(int i) { return i >= 0 && i < L; }

    static void C(DS a) { E(a); }
    static void C(DS a, DS b) { E(a, b); }
    static void C(DS a, DS b, DS c) { E(a, b, c); E(a, c, b); E(b, c, a); }
    static void C(DS a, DS b, DS c, DS d) {
        E(a, b, c, d); E(a, c, b, d); E(a, d, b, c);
        E(b, c, a, d); E(b, d, a, c); E(c, d, a, b);
    }

    static void D(DS a) {
        if (a.isInt()) {
            int i = s(Math.round(a.d));
            if (isIn(i) && (s[i] == null || s[i].length() > a.s.length()))
                s[i] = a.s;
        }
    }
    static void D(DS a, DS b) {
        C(a.add(b)); C(a.mul(b)); C(a.sub(b)); C(b.sub(a));
        C(a.div(b)); C(b.div(a)); C(a.pow(b)); C(b.pow(a));
    }
    static void D(DS a, DS b, DS c) {
        C(a.add(b),c); C(a.mul(b),c); C(a.sub(b),c); C(b.sub(a),c);
        C(a.div(b),c); C(b.div(a),c); C(a.pow(b),c); C(b.pow(a),c);
    }
    static void D(DS a, DS b, DS c, DS d) {
        C(a.add(b),c,d); C(a.mul(b),c,d); C(a.sub(b),c,d); C(b.sub(a),c,d);
        C(a.div(b),c,d); C(b.div(a),c,d); C(a.pow(b),c,d); C(b.pow(a),c,d);
    }

    static void E(DS a) { D(a); if (a.isFac()) D(a.fac()); }
    static void E(DS a, DS b) {
        D(a, b);
        if (a.isFac()) { D(a.fac(), b); D(a.fac().fac(), b); }
        if (b.isFac()) { D(a, b.fac()); D(a, b.fac().fac()); }
        if (a.isFac() && b.isFac()) {
            D(a.fac(), b.fac()); D(a.fac().fac(), b.fac().fac());
            D(a.fac().fac(), b.fac()); D(a.fac(), b.fac().fac());
        }
    }
    static void E(DS a, DS b, DS c) {
        D(a, b, c);
        if (a.isFac()) { D(a.fac(), b, c); D(a.fac().fac(), b, c); }
        if (b.isFac()) { D(a, b.fac(), c); D(a, b.fac().fac(), c); }
        if (a.isFac() && b.isFac()) {
            D(a.fac(), b.fac(), c); D(a.fac().fac(), b.fac().fac(), c);
            D(a.fac().fac(), b.fac(), c); D(a.fac(), b.fac().fac(), c);
        }
    }
    static void E(DS a, DS b, DS c, DS d) {
        D(a, b, c, d);
        if (a.isFac()) { D(a.fac(), b, c, d); D(a.fac().fac(), b, c, d); }
        if (b.isFac()) { D(a, b.fac(), c, d); D(a, b.fac().fac(), c, d); }
        if (a.isFac() && b.isFac()) {
            D(a.fac().fac(), b.fac().fac(), c, d); D(a.fac(), b.fac(), c, d);
            D(a.fac().fac(), b.fac(), c, d); D(a.fac(), b.fac().fac(), c, d);
        }
    }
    
    public static void main(String[] args) {
        C(new DS(1), new DS(2), new DS(3), new DS(4));

        int n = 0;
        for (int i = MIN; i <= MAX; ++i)
            if (s[s(i)] != null) {
                System.out.println(i + " = " + s[s(i)]);
                ++n;
            }

        System.out.println("\n" + n);
    }
}

I admit this code is rather ugly, but it was a quick hack. Maybe there are more numbers in [-100,100] that can be formed this way. Feel free to try out by implementing the possible application of more than two faculties to a DS. Furthermore it's possible (but not likely) that integer targets were rejected by round-off errors.

Thanks for the competition


milagros: i get 306 integers in [-200,200], the same number as you including -26. I missed -55 first and only realised my mistake by accident, but in time =P
grats

[Smibu]

Hhahhaha, you programmed a program for this, like mila did too! :DD
Nice code there btw, I don't understand much of it, though. I Should learn the syntax :P
Maybe mila could show his code too?

[welle]

sure, ez miss some numbers doing it manually. but grats to nom for finding so many...
i guess zebra wrote program too?
ye mila, please show your code =)

[teajay]

laoal it's funny how competition gets the best out of people.

[zebra]

sure, ez miss some numbers doing it manually. but grats to nom for finding so many...
i guess zebra wrote program too?
ye mila, please show your code =)

haha ye i wrote a program too, in c++ btw
The 7 wrong numbers i had only didn't have correct brackets, which was due to an error in my program. I didn't have time to check the formulas through, because i started writing the program so late (it took about 4 hours). Maybe I correct the bug and release it here later if someone is interested.

[welle]

Maybe I [...] release it here later if someone is interested.

yes of course.

Which are the two numbers you missed?

[nick-o-matic]

Omg xiit hacking

Hopefully I will learn to code something like that. I should take courses in near future.

sure, ez miss some numbers doing it manually. but grats to nom for finding so many...

Thx, I thinked this for a while I could say. I tried systematically go through all combinations, i mean tried to get everything out of for excample 4! once took it under work.

[zebra]

Maybe I [...] release it here later if someone is interested.

yes of course.

Which are the two numbers you missed?

Seems that they were -99 and 99. Dunno why
I don't have time to look at the code now but I'll upload it for you in few days.

[nick-o-matic]

New battle?

[Smibu]

Yes!

Imagine a 7x7 grid. Start by placing number 1 in any of the 49 squares. Then place the second number (2) in another square so that:
1. You jump three squares vertically or horizontally from number 1 and place number 2 there, or
2. You jump two squares diagonally from number 1 and place number 2 there.

Only these two choices are allowed. For example, you cannot jump 3 squares diagonally or 2 squares vertically/horizontally.

Then loop the same thing with 3,4,5,... by jumping from the previous number as long as it is possible (you can only jump to an empty square, and you can't "bounce" from the grid's borders or anything, and you can't teleport to the opposite side).

XXX2XXX
X2XXX2X
XXXXXXX
2XX1XX2
XXXXXXX
X2XXX2X
XXX2XXX

In this example, number 1 has been placed in the centre of the grid. Those eight 2's represent the POSSIBILITIES where you could place number 2 (X=empty square).

I'll give two different challenges:
1. Try to place as many numbers as possible in the grid (maximum=49 (or less), I'm not sure if it's possible to place all).
2. Try to place as few numbers as possible so that it's still impossible to place any more.

Battle over because three people solved this already, see below!

By the way, that kind of grid that is written in text form is bad when you have both two-digit and one-digit numbers, so please send your answers in a form that I can understand. Good luck, ask here if you've got questions! :)

[Smibu]

Hmm, there have been some misunderstandings about the rules, I'll give a better example here of how it should be done:



The result in that grid is 22 numbers. You cannot jump to any square from number 22 anymore.

Got it??? :P

Btw, here's a blank grid for everyone. You can use this grid to post your answers! (Use Paint for placing the numbers in there, for example)

[zebra]

Hi welle and others,
here is the source code of my program and the program itself.
The program first asks the numbers you want to calculate with and then generates formulas.txt and writes all numbers there.
I fixed the error which was there and did some other tiny things.

The program works so that first it forms all different kind of combinations of the given numbers and after that tried all kinds of different combinations of calculations between them.
It's not very well tested so there might be some bugs left, like overflows of the numbers etc.

[welle]

thank you. very nice

[Smibu]

Okay, three people solved this one already so I think it's practically useless to continue this battle anymore, it was easier than I thought.

Battle over, results:

1. milagros 49/6 (sent 28 Aug 2008, 21:12)
2. welle 49/6 (sent 28 Aug 2008, 22:12)
3. nick-o-matic 49/6 (sent 28 Aug 2008, 23:13)

This battle was pretty tight!
Here's the solved grids, everyone had different ones (not too surprising, though):

[welle]

i solved it by finding an hamiltonian path in this graph:

dame, should have started earlier

[Mawane]

Martin Gardner,
"A Pride of Problems, Including One that is Virtually Impossible",
Scientific American,
Volume 241, December 1979:
The Impossible Problem. This beautiful problem, which I call "impossible" because it seems to lack sufficient information for a solution, began making the rounds of mathematics meetings a year or so ago. I do not know its origin. Mel Stover of Winnipeg was the first to call it to my attention.

Two numbers (not necessarily different) are chosen from the range of positive integers greater than 1 and not greater than 20. Only the sum of the two numbers is given to mathematician S. Only the product of the two is given to mathematician P.

On the telephone S says to P: "I see no way you can determine my sum."

An hour later, P calls back to say: "I know your sum."

Later S calls P again to report: "Now I know your product."

What are the two numbers?

To simplify the problem, I have given it here with an upper bound of 20 for each of the two numbers. This means that the sum cannot be greater than 40 or the product greater than 400. If you succeed in finding the unique solution, you will see how easily the problem can be extended by raising the upper bound. Surprisingly, if the bound is raised to 100, the answer remains the same. Stover tells me that a computer program in Israel checked on all numbers up to two million without finding a second solution. It may be possible to prove that the solution is unique even if there is no upper bound whatsoever.

Don't underestimate this impsy problem** comments welcomed
Anwser is there: http://people.scs.fsu.edu/~burkardt/fun ... ution.html

[welle]

I like the original problem even more:

• Let x and y be two integers with 1<x<y and x+y≤100. Sally is given only their sum x+y and Paul is given only their product xy. Sally and Paul are honest and all this is commonly known to both of them.
  
  The following conversation now takes place:
  • Paul: I do not know the two numbers.
    Sally: I knew that already.
    Paul: Now I know the two numbers.
    Sally: Now I know them also.
  
  What are the numbers?

And I think you shouldn't have posted the solution immediately, but thanks for reviving this topic.

[Mawane]

I like the original problem even more:

• Let x and y be two integers with 1<x<y and x+y≤100. Sally is given only their sum x+y and Paul is given only their product xy. Sally and Paul are honest and all this is commonly known to both of them.
  
  The following conversation now takes place:
  • Paul: I do not know the two numbers.
    Sally: I knew that already.
    Paul: Now I know the two numbers.
    Sally: Now I know them also.
  
  What are the numbers?

And I think you shouldn't have posted the solution immediately, but thanks for reviving this topic.

I posted answer here cuz people could just search on the web for the answer and ez xiit by saying they found by themselves

[nick-o-matic]

Mawane's previous battle was very nice indeed, pretty ideal actually. Not any programming skills or education required and still fun. Too bad it killed the topic though.

Here's a new one, not so hard but fun: a balloon has been attached to the bottom of a box of water with a string. In the rest the situation looks like this:

Then we give the box of water acceleration a. (the box is located in a car or something)
Now what happens to the balloon (after we have waited a bit for stabilization ofc)?

[Bismuth]

I'd say it will stay as it is in the bowl, but I may be wrong.

[nick-o-matic]

I'd say it will stay as it is in the bowl, but I may be wrong.

Yes, you are wrong.

[Igge]

I'm not sure, but I'm gonna guess:

As the car accelerates, the water will be "accelerated" in the opposite direcrion (-a). Since the balloon is less dense than water, it will get pushed away by the water that is gathering to the left in the bowl, and will thus get pushed to the right (a). However, when the water settles, and returns to it's original state, the ballon will do the same.

[nick-o-matic]

I'm not sure, but I'm gonna guess:

As the car accelerates, the water will be "accelerated" in the opposite direcrion (-a). Since the balloon is less dense than water, it will get pushed away by the water that is gathering to the left in the bowl, and will thus get pushed to the right (a). However, when the water settles, and returns to it's original state, the ballon will do the same.

Yes, it will get pushed to the right, but I'd like to see a bit more exact answer, like calculating the angle =)

[Igge]

Count me out then. 8)

[Bismuth]

I didn't want to think, but yeah, it's very obvious, nab me