All Questions
92
questions
1
vote
0
answers
71
views
Worst-case minimization of size of intersection of an offset set with a given set
Consider the set of first $N$ natural numbers i.e., $S_N$ = $\{1,2,3, \dots,N\}$. Let $S^k$ be a finite subset of $S_N$, where $|S^k|$ = $k$. We define another set $O$ whose elements $\in$ $\{0,1,2,\...
- 104
2
votes
1
answer
1k
views
Greedy algorithms: why does no optimal solution for smaller coins mean that the greedy algorithm must work?
I'm reading Competitive Programmer’s Handbook. They take the Euro to perform analysis on a greedy algorithm.
For example, if the coins are the euro coins (in cents)
{1,2,5,10,20,50,100,200} and n ...
- 149
2
votes
3
answers
209
views
Iterating over all squarefree composites $\lt L$
I need to iterate over all integers that are:
Composite
Squarefree
Smaller than a limit $L$
And see for each one if it has a certain property (in addition to these 3). Then I need to sum all such ...
- 1,022
2
votes
1
answer
163
views
Find two subsets with a common sum in two sequences
For a positive integer $n$ and two integer sequences $a_1,a_2...a_n$ and $b_1,b_2...b_n$ where $\forall i$, $a_i,b_i \in [1,n]$, I want to find two non-empty subsets, one in each sequence, with the ...
- 232
4
votes
1
answer
195
views
Combinations of red and black balls
Given $N$ Identical Red balls and $M$ Identical Black balls, in how many ways we can arrange them such that not more than $K$ adjacent balls are of same color.
Example : For $1$ Red ball and $1$ ...
- 41
0
votes
1
answer
64
views
Construct a positive decimal number of length $n$ or less that is divisible by $2^n-1$ for n in $Z^+_0$
I got this question on a discrete mathematics test and I no idea on how to solve it:
Create a method for constructing a positive decimal number of length $n$ or less with digits from set $\{0,1,8,9\...
1
vote
0
answers
57
views
What does the 8 stand for in the Cantor pairing function?
What does the "8" stand for in the Cantor pairing function (which assigns a natural number to each pair of natural numbers)?
Can I change it, or is it constant?
The other function for getting the ...
- 17
5
votes
2
answers
191
views
Pigeonhole principle based algorithm
I was trying to solve this problem.
http://olympiads.hbcse.tifr.res.in/olympiads/wp-content/uploads/2016/09/inmosol-15.pdf
INMO-2015 P6. From a set of $11$ square integers, show that one can choose ...
0
votes
1
answer
39
views
Groups with the same amount
Let there be an array of digits $ [0,0,1,1,2,2,\ldots,9,9] $, how many ways to split this array into two subarrays, so that the sum of numbers in the subarrays is different by a multiple of $11$?
...
- 1,074
1
vote
2
answers
216
views
Given an integer, how many ways can you divide into unequal portions
I have been thinking about this problem for a while but have been unable to formalize a complete answer.
Given an integer $n \geq 3$, how many different sets can you sum the integer elements in the ...
- 111
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
1
vote
1
answer
168
views
Generative function for Goldbach's conjecture
I have written a procedure that, given an integer n, it comes out the polynomial with its coefficients are prime and odd $\leq $ n
For example, procedure(5)= $x^{5}+x^{3}+x^{2}$, procedure(10)=$x^{7}+...
- 580
2
votes
2
answers
114
views
How to check if $k$ divides $\binom {n - 1} {k - 1}$ cheaply?
I'm writing a computer algorithm to do binomial expansion in C#. You can view the code here; I am using the following identity to do the computation:
$$
\dbinom n k = \frac n k \dbinom {n - 1} {k - 1}...
- 353
1
vote
0
answers
57
views
Number of subsets with constraint
How many subsets $P$ of $\{1, 2, ..., n\}$ are there such that if $x$ belongs to $P$ then $2x$ and $3x$ don't belong to $P$? For example, if $n = 4$ then there are $8$ such subsets (empty subset + $\{...
- 1,591
2
votes
0
answers
86
views
Find subset of size $k$ such that it maximizes the metric distance of the elements.
Suppose I have a set $A=\{a_1,a_2,...,a_n\}$ and a metric $f$ on $A$. I want to extract a subset $B$ of size $k$ such that it maximizes the sum of the distances between every possible pair in B. i.e. ...
- 2,457