Proof contest

t0rajir0u

Er... you gave us inverses and want us to prove inverses?

**Posted:** Sat Aug 16, 2008 1:30 am

_________________
Annoying Precision (http://qchu.wordpress.com/)

Altheman

They exist, but we don't know that they are in $S$ .

If we have a set $\{1\}$ and the operation is addition, we know that $-1$ exists...but it is not necessarily in $S$ .

**Posted:** Sat Aug 16, 2008 1:59 am

Rzeszut

Denote $ab: = a\triangle b$ . If $S = \left\{s_{1},\ldots,s_{n}\right\}$ , then $xS: = \left\{xs_{1},\ldots,xs_{n}\right\}\subset S$ and since $xs = xs'\implies x^{ - 1}xs = x^{ - 1}xs'\implies s = s'$ , we have $\#\left(xS\right) = \#S$ and thus $xS = S$ . Therefore $e\in xS$ , i.e. $x^{ - 1}\in S$ .

**Posted:** Sat Aug 16, 2008 2:07 am

_________________
$\left(\int_{I}f(t)dt\right)^{k}= \int_{I^{k}}f(t_{1})\cdot\ldots\cdot f(t_{k}) dt_{1}\ldots dt_{k}$

t0rajir0u

**Posted:** Sat Aug 16, 2008 2:26 am

_________________
Annoying Precision (http://qchu.wordpress.com/)

Altheman

Ahh right...good point! I suppose that I was being lazy. I was thinking that the properties were covered, but we still need associativity for $x^{-1}$ or whatever we want to call it. I suppose I was just being lazy when I converted the problem (a finite subset of a group is a group if it is closed). I will edit. Also why is there a solution here already?

**Posted:** Sat Aug 16, 2008 2:32 am

_________________
-Alex
Altheman's Problem Column

t0rajir0u

The problem is indeed false if the fourth condition is removed entirely (in other words, a finite monoid is not necessarily a group). For example, the set of functions from a finite set to itself forms a finite monoid under composition but inverses clearly do not exist since there are plenty of non-surjections.

Rzeszut's solution is quite suspect unless a larger set is specified; it's not at all clear what set the expression $x^{ - 1} xs$ belongs to, even if it is "given" that it evaluates to $s$ . The closest salvage to his proof (and the statement that you probably want, which generalizes the problem you converted) is the statement that a finite monoid with the cancellation property is a group, which is what I mean when I say that inverses can exist formally.

Edit: I should mention that the identity also only needs to exist formally; in other words, the third condition can be dropped, and in other other words, a finite semigroup with the cancellation property is a group.

**Posted:** Sat Aug 16, 2008 2:44 am

_________________
Annoying Precision (http://qchu.wordpress.com/)

RightAnnihilator

Good elementary problem! Smile

Glad to see some abstract algebra anytime...

BTW Altheman, edit in there that H is nonempty.

For those of you currently working on this: Rzeszut's post does not appear to constitute a proof, but that may be due to edits to the original problem after he posted. For one thing, S is not assumed to be finite, H is, and I don't see where x comes from. However if we suppose his S is supposed to be H, and his x is also from H, then what he has written contains the important clue to the inverse problem.

What is $\#S$ supposed to denote? EDIT: Cardinality? Hrm, come to think of it I might have run across that in a compsci book somewhere.

The step that shows inverses (and identity) is quite straightforward, and it's not necessary to resort to mappings.

**Posted:** Sun Aug 17, 2008 6:48 pm

RightAnnihilator

So anyway, shall we post a solution and continue?

It would be good to issue something once every 5 days or so. And if I could help out by coming up with some problems of appropriate difficulty, just lemme know by PM.

**Posted:** Mon Aug 25, 2008 4:12 pm

1=2

A convex quadrilateral $ABCD$ with area $2002$ contains a point $P$ in its interior such that $PA=24$ , $PB=32$ , $PC=28$ , and $PD=45$ . Find the perimeter of $ABCD$ .

Also, there is a fact that pwnes the problem instantly, please prove it if you use it.

**Posted:** Tue Aug 26, 2008 6:05 am

_________________
Hmm... apparently quoting Disney movies gets me muted on FTW. Razz

RightAnnihilator

Did you purposely mean for one of the sides to have an irrational length? To make sure we computed it correctly?

**Posted:** Wed Aug 27, 2008 8:13 pm

1=2

I didn't make this problem. This was a problem on one of the AMC 12's in 2002.

**Posted:** Thu Aug 28, 2008 8:13 am

_________________
Hmm... apparently quoting Disney movies gets me muted on FTW. Razz

RightAnnihilator

Ok great thanks.

So, the answer DOES contain an irrational summand? I thought usually they make the numbers come out something reasonable.

**Posted:** Thu Aug 28, 2008 7:22 pm

Rofler · Yang-Mills Theory Offline Joined: 10 Mar 2007 Posts: 572

Well, it's AMC, so let's just make every angle a right angle Wink

**Posted:** Thu Aug 28, 2008 9:22 pm

1=2

**Posted:** Fri Aug 29, 2008 8:53 am

_________________
Hmm... apparently quoting Disney movies gets me muted on FTW. Razz

Rofler · Yang-Mills Theory Offline Joined: 10 Mar 2007 Posts: 572

Well, the area of the quad=
$PAB+PBC+PCD+PDA\le absin\theta_1/2+bcsin\theta_2/2+cdsin\theta_3/2+dasin\theta_4/2$ with each $theta_i$
between 0 and 360.

But $sin\theta_i \le 1$ w/ equality iff theta = 90, so $xysin\theta_i/2 \le xy/2$ with equality if $i=90$ .

Summing cyclically, we have

$absin\theta_1/2+bcsin\theta_2/2+cdsin\theta_3/2+dasin\theta_4/2 \le ab/2+bc/2+cd/2+da/2=2002$ with equality iff each $theta_i=90$ hence PA is perp. to PB which is perp. to PC which is perp. to PD.

Therefore, you can find the perimeter by simple pythagoras.

**Posted:** Fri Aug 29, 2008 10:59 am

RightAnnihilator

Yeah, after noticing that a quadrilateral with perpendicular diagonals those lengths had area 2002, I wondered if it wasn't going to turn out that 2002 was somehow a maximal area for those particular parameters, forcing P to be the intersection of the diagonals.

This doesn't seem like a fact that would "pwn the problem instantly". I still wonder what that's supposed to be...

**Posted:** Sat Aug 30, 2008 3:59 pm

1=2

the fact is that the diagonals are perpendicular, and meet at P.

**Posted:** Sat Aug 30, 2008 4:32 pm

_________________
Hmm... apparently quoting Disney movies gets me muted on FTW. Razz

Altheman

Problem 4:

Definition 1: $\mathbb{N}$ is a set with the following properties:

i) $1\in \mathbb{N}$
ii) If $n\in \mathbb{N}$ , then there is a unique number $n'\in \mathbb{N}$ called the successor of $n$ .
iii) If $m,n\in\mathbb{N}$ and $m' = n'$ , then $m = n$ .
iv) For any $n\in \mathbb{N}$ , $n'\ne 1$ .
v) If $S$ is a subset of $\mathbb{N}$ and we have
---a) $1\in S$
---b) $n\in S\implies n'\in S$
then $S = \mathbb{N}$ .

Definition 2: For all $n\in \mathbb{N}$ 'assign'

and if $m + n$ is assigned, then

Prove that: the operator $+$ in def. 2 can be extended to a unique operation such that for all $m,n\in \mathbb{N}$ , we have
i) $m + 1 = m'$
ii) $(m + n)' = m + n'$

Comment: The word 'assign' is used loosely. $+$ should be more rigorously defined as a function.

**Posted:** Sun Sep 07, 2008 9:44 am

_________________
-Alex
Altheman's Problem Column

chess64

5 The equation $x^3+ax^2+bx+c = 0$ has three real roots for some $a,b,c \in \mathbb{R}$ . Show that if $-2 \le a+b+c \le 0$ , at least one of these roots lies in the interval $[0,2]$ .

Please turn in something by next friday.

**Posted:** Fri Oct 17, 2008 4:39 pm

chess64

you say you want to participate but you never do.

this problem was from Russia 2008.

**Posted:** Sat Oct 25, 2008 12:25 pm