Tag: prove

Prove that $\forall \ A_k\subset [3n]$, with $|A_k|=2n$, $\exists\ a_i,\ a_j\in A_k\ $ s.t. $\ a_i-a_j=n-1$


Let $ n\geq2$ be an integer. Prove that every subset $ A_k\subset [3n]$ , with $ |A_k|=2n$ , contains two elements $ a_i,\ a_j\ $ s.t. $ \ a_i-a_j=n-1$ , and prove that $ \nexists\ a_i,\ a_j \in A_k\ \forall k\ $ s.t. $ \ a_i – a_j =n$ .

It seems obvious that I will have to apply the Pigeonhole Principle, but I have no clear idea about how to start. Could you give me some hints? Thanks in advance!

Let f be a function defined on a nbhd of 0 w/ the property that |f(x)| ≤ x^2 for all x. Prove that f is differentiable at 0 and calculate f'(0).

Let f be a function defined on a neighborhood of 0 with the property that |f(x)| ≤ x^2 for all x. Prove that f is differentiable at 0 and calculate f'(0).

I have started this problem by first letting I be a nbhd of 0. Then I let x be an element of I/{0}. I am pretty sure I then must show the limit exists and evaluate it at 0. However, I am not sure how to show it is defined at 0 with just the fact that |f(x)| ≤ x^2 for all x.

Prove that $\frac{x+y}{1+xy}$ is an Abelian Group

Let $ I=\left]-1,\ 1\right[$ be an interval, and $ \left(I,\ \star\right)$ be a magma such that:

$ $ \left(\forall\ \left(x,\ y \right) \in I^2\right)\ x \star y=\frac{x+y}{1+xy}$ $

I need to prove that $ \left(I,\ \star\right)$ is an Abelian group.

A simple way to prove it is by checking that the magma $ \left(I,\ \star\right)$ satisfies the group axioms including commutativity.

Based on the following statement I would like to approach that problem:

Let $ f$ be a homomorphism from $ \left(X,\ \perp \right)$ to $ \left(I,\ \star\right)$ , then the algebraic structure of $ \left(I,\ \star\right)$ is exactly the algebraic structure of $ \left(X,\ \perp \right)$

So I would like to find out a usual Abelian group – ex. $ \left(\mathbb{R},\ +\right)$ – and a homomorphism $ f$ from that group to $ \left(I,\ \star\right)$ .

Assume that $ f$ is a homomorphism from $ \left(X,\ \perp \right)$ to $ \left(I,\ \star\right)$ , then

$ $ \left(\forall\ \left(x,\ y \right) \in X^2\right)\ f\left(x \perp y \right)= f\left(x\right) \star f\left(y \right)$ $

$ $ \Leftrightarrow f\left(x \perp y \right)= \frac{f\left(x\right) + f\left(y \right)}{1+f\left(x\right) \cdot f\left(y \right)}$ $

I got stuck on that. Could anyone support me with some hints how to get it done.

If $f\geq0 , f(0)=f(1)=0$,and $\int_0^1f”/f dx$ exists,how to prove $\int_0^1f”/f dx\geq \pi^2$

If $ f\geq0 , f(0)=f(1)=0$ ,and $ \int_0^1f”/f dx$ exists,how to prove $ $ \int_0^1\frac{f”}{f}dx\geq \pi^2$ $

The lower bound $ \pi^2$ was guessed by myself, if it was not true ,then how to find this lower bound ?

My way is to have an analytic extension with $ T=2$ , and use the Fourier Series to have an evaluation .

But it seems like that I was wrong.

Prove that if string_is_prefix returns true, then the string has a length as big as the prefix

I’m trying to create a version of string_is_prefix that prove that a string is longer than the prefix if it returns true. Here’s the code I have so far:

#include "share/atspre_staload.hats"  dataprop StringLen(bool) =     | LessThan(false)     | {m,n:nat | m >= n} GreaterThanEqual(true)  fun string_is_prefix {m, n: nat} (string_prefix: string(m), string: string(n)): [b:bool] (StringLen(b) | bool(b)) =     let val prefix_len = string_length(string_prefix)         val string_len = string_length(string)         fun is_prefix {i: nat | m <= n; i < m} (index: size_t(i)): [b:bool] bool(b) =             let val equal = g1ofg0(string_get_at(string, index) = string_get_at(string_prefix, index))             in                 if index + 1 >= prefix_len then                     equal                 else                     equal * is_prefix(index + 1)             end     in         if prefix_len > string_len then             (LessThan() | false)         else if prefix_len > 0 then             let val result = is_prefix(i2sz(0))             in                 if result then                     (GreaterThanEqual{n, m}() | result)                 else                     (LessThan() | result)             end         else             (GreaterThanEqual{n, m}() | true)     end  fun func(string: stringGte(1)) =     ()  implement main0(argc, argv) = {     val prefix_string: string(1) = "t"     val string: [n:nat] string(n) = g1ofg0(argv[0])     val (pf | is_prefix) = string_is_prefix(prefix_string, string)     val () =         if is_prefix then             let prval GreaterThanEqual{n, m}() = pf             in                 func(string)             end }

Unfortunately, the call to func(string) does not compile as if this proof was not working:

unsolved constraint: C3NSTRprop(C3TKmain(); S2Eapp(S2Ecst(>=); S2EVar(5277->S2Evar(n$  8654(14309))), S2Eintinf(1)))

How can I make this proof work?

How to prove that the time complexity of this algorithm is O($\sqrt{N}$)?

  int n;   cin >> n;   int sum = 0;   for (int i = 1; sum <= n; i++) {       sum += i;   }

If I assumed that $ N = 100$ , the loop will run $ 13$ steps, which is almost the square root of $ N$ , if $ N = 10000$ , the loop will run $ 141$ steps, which is almost the square root of $ N$ , but I don’t know how to prove that, I only know it by intuition