All Questions
103
questions
22
votes
6
answers
539
views
Proving surjectivity of some map from a power set to a subset of integers.
We assign to every element $i$ from $N=\{1,2,...,n\}$ a positive integer $a_i$. Suppose $$a_1+a_2+...+a_n = 2n-2$$ then prove that map $T: \mathcal{P}(N) \to \{1,2,...,2n-2\}$ defined with $$T(X) = \...
- 90.7k
15
votes
0
answers
272
views
Recovering a binary function on a lattice by studying its sum along closed paths
I have a binary function $f:\mathbb N^2\rightarrow\{0,1\}$. While I do not known $f$ explicitly, I have a "device" located at the origin $(1,1)$ which can do the following:
Given an even ...
- 4,333
8
votes
2
answers
3k
views
Placing n points in a MxM square grid
I am facing an apparently well-known problem: placing $n$ points in a discrete grid so that the points are 'evenly' distributed. By evenly I mean that I would like the density of points to be nearly ...
- 81
8
votes
2
answers
1k
views
Algorithm for least required matches to rank players in tournament
Assuming the following conditions:
A higher skill level always beats a lower skill level.
Given n players, each have a distinct skill level compared to the other (n-1).
If player A has beat player B, ...
7
votes
1
answer
126
views
In this checkerboard problem, is there a way to tell if any two situations are equivalent?
There is an infinite square grid chessboard with chess pieces placed on certain squares. There is at most one piece in a grid.
We can perform the following operations each time:
Split: Select a chess ...
- 71
6
votes
4
answers
3k
views
What's the number of decibinary numbers that evaluate to given decimal number?
Let's define a decibinary number system, where each bit (or digit) can range from $0$ to $9$, but it's place value corresponds to the one in the binary system. For example:
$$(2020)_{decibinary} = 2 \...
6
votes
2
answers
214
views
a semi-hard problem on combinatory
I ran into a nice interview question.
the problem is as follows:
We have array of $n$ integers. for $1 \leq i \leq j \leq n$. we want to set $c_{ij}$= Sum of all values in the range $i$ to $j$ of ...
user871754
5
votes
2
answers
656
views
Construct $4 \times 4$ magic square with fixed "1"
The method I have found to generate $4\times 4$ magic squares gives me a result in which the number "1" is at of the corners of the square. How can we extend this to a method to generate a magic ...
- 2,760
5
votes
1
answer
848
views
How many ways are there to bag the marbles?
Suppose we have $n$ marbles each tagged with numbers $1$ through $n$. We have bags which are allowed to contain things where a thing is defined as either $\text{(a)}$ a marble or $\text{(b)}$ another ...
- 12.8k
5
votes
2
answers
634
views
Count Number of Sequences
The question is:
Given a sequence of positive integers A={1,2,3,...,N}. Count the number of sequences you can get after making K swaps between adjacent element on it for a given N ?
My approach:
My ...
- 61
5
votes
0
answers
45
views
Number of lines of $3$ points in an arrangement of points and lines
It is well known that a finite set of $n$ points cannot form more than
$$\bigg\lfloor \frac{n(n-3)}{6} \bigg\rfloor+1 $$
lines that include $3$ points. Would this result still hold if we assume that ...
user920720
4
votes
2
answers
195
views
Finding counterfeit coins
Suppose I have $N$ rare coins, of which $M \le N$ are counterfeits. I am blind. I ask an oracle who charges me a penny to tell me in yes/no answers whether there is a counterfeit in any group I show ...
- 555
4
votes
1
answer
285
views
Printing neatly
I'm working on the following problem (which is not my actual question)
Consider the problem of neatly printing a paragraph with a monospaced font (all
characters having the same width). The input ...
- 910
4
votes
1
answer
1k
views
Algorithm for generating restricted integer composition of N in k parts from interval [a,b] given the lexicographic number.
Consider the restricted compositions of $6$ in four parts from integers $\{1, 2, 3\}$.
...
- 525
4
votes
1
answer
380
views
What is the minimum number of squares to be drawn on a paper in order to obtain an 8x8 table divided into 64 unit squares? [closed]
What is the minimum number of squares to be drawn on a paper in order to obtain an $8\times8$ table divided into $64$ unit squares.
Notes:
-The squares to be drawn can be of any size.
-There ...
- 63