Finite or infinite

2.6

10 votes
Algorithms, Math, Number Theory, Number theory
Problem

You are given the following:

  • A set S of size n
  • A class of functions called FUNC f:CC such that  kS,fk(x)=x holds  x
  • A set G that is defined based on the natural numbers such that a number lG if and only if fl(x)=xx holds fFUNC

Your task is to construct the complement set of G based on the natural numbers, which implies that a number lG if and only if lG

If the cardinality of G is finite, then print FINITE. Otherwise, print INFINITE. There are multiple test cases.

Mathematics note

  • f:CC is a notation that is used to describe a function f that considers a complex number, a+ib, as an input and provides another complex number, c+id, as the output.
  •  is read as for all, particularly if fl(x)=xx which implies that fl(x)=x is true for all x in the domain of the function. Here, domain is a complex number.
  • fl(x)=f(f(f(..f(x))) where f is repeated l times which means that f2(x)=f(f(x)),f3(x)=f(f(f(x))).
  •  is used to denote a set that is a subset of another set.
  • Cardinality is used to denote the size of a set.

Input format

  • First line: t denoting the number of test cases
  • For each test case:
    • First line: n denoting the size of the set S 
    • Second line: n elements of set S

Output format

For each test case, print the string FINITE or INFINITE in a single line.

Constraints

1 sum of n over all the test cases 100000

If kS, then 1k100000

Time Limit: 5
Memory Limit: 256
Source Limit:
Explanation

The sample has two test cases.

In first testcase, we have the information that f(x)=x,f2(x)=x,f4(x)=x, Note that, from f(x)=x we can show that fm(x)=x, mN. First, let us prove that f3(x)=x holds. f(f(f(x)))=f(f(x))=f(x)=xf3(x)=x, where we used the fact f(x)=x repeatedly. In a similar manner, we can prove the claim that fm(x)=xmN. Hence, we get that for all mN, mG. Thus, G is an empty set, and the answer is FINITE.

 

In the second testcase, we will prove that the set G is exactly all the even positive numbers, i.e. f2m(x)=x. We can get this claim from a similar inductive argument as above. Now, all we need to prove is that odd numbers are not part of G. Consider the simple function f(x)=1x, which satisfies the condition for all even positive integers (hence it belongs to class FUNC), but it does not satisfy f2m1(x)=x for any positive integer m. Hence, G, the complement of G is exactly the set of odd numbers, and thus the answer is INFINITE.

 

Updated problem name

Finite or infinite sets

Updated problem statement

You are given the following:

  • A set S of size n
  • A class of functions called FUNC f:CC such that  kS,fk(x)=x holds  x
  • A set G that is defined based on the natural numbers such that a number lG if and only if fl(x)=xx holds fFUNC

Your task is to construct the complement set of G based on the natural numbers, which implies that a number lG if and only if lG

If the cardinality of G is finite, then print FINITE. Otherwise, print INFINITE. There are multiple test cases.

Mathematics note

  • f:CC is a notation that is used to describe a function f that considers a complex number, a+ib, as an input and provides another complex number, c+id, as the output.
  •  is read as for all, particularly if fl(x)=xx which implies that fl(x)=x is true for all x in the domain of the function. Here, domain is a complex number.
  • fl(x)=f(f(f(..f(x))) where f is repeated l times which means that f2(x)=f(f(x)),f3(x)=f(f(f(x))).
  •  is used to denote a set that is a subset of another set.
  • Cardinality is used to denote the size of a set.

Input format

  • First line: t denoting the number of test cases
  • For each test case:
    • First line: n denoting the size of the set S 
    • Second line: n elements of set S

Output format

For each test case, print the string FINITE or FINITE in a single line.

Constraints

1 sum of n over all test cases 100000

If kS, then 1k100000

Editor Image

?